A sequence Problem

[hqt]

I have this problem and haven't solve it, yet. who has any idea, please give me :)
the problem is: give a sequence with n elements (n<=10^6), for example 4 3 2 1 and 2 number L,R (left and right)
count how many pair (i,j), i<=j that:

L<=A[i]+A[i+1]+..+A[j]<=R

someone will think this problem is easy, but the normal solution is O(n^2), and it will be run in long time. (limit is 3s). So, anyone else has some idea. I think this problem can solve in O(NlogN).

thnask ;)

[TrustyTony]

Logical for me is:
All element between limits are solutions, and then you can consider those subsequences 2..j-i (or going over R for sum) length where that element is value with smallest index.

Does not look O(n^2) for me.

[Momerath]

Not sure what you consider the normal solution, but you only have to iterate through the list one time giving an O(n) solution. Not sure what craziness you'd have to do to make it O(n^2).

Given array A[], L and R.

If L > R output 0 and stop
Set count = 0, i = 0, j = 0
While i < length of A[]
    If A[i} >= L then
        j = i
        While j < length of A[] and A[j] <= R
            Increment j
        End While
        count = count + SpecialSum(j-i)
        i = j - 1
    End If
    Increment i
End While
Output count

Function SpecialSum(int n)
    return n * (n + 1) / 2
End Function

The only thing you might not recognize is SpecialSum, which is the sum of the numbers from 1 to n. If you look at a range that qualifies you find this:

Using the numbers 1 through whatever to represent the values of the range, it doesn't matter really what the values are, it's just easier to use these values

Numbers in range : 1 (List = 1)
Qualifying groups : (1)
Number of Groups : 1 = 1

Numbers in range : 2 (List = 1 2)
Qualifying groups : (1) (2) (1 2)
Number of Groups : 3 = 1 + 2

Numbers in range : 3 (List = 1 2 3)
Qualifying groups: (1) (2) (3) (1 2) (2 3) (1 2 3)
Number of Groups : 6 = 1 + 2 + 3

Numbers in range : 4 (List = 1 2 3 4)
Qualifying groups: (1) (2) (3) (4) (1 2) (2 3) (3 4) (1 2 3) (2 3 4) (1 2 3 4)
Number of Groups : 10 = 1 + 2 + 3 + 4

You can continue this if you wish, but that should give you the idea. Also the sum of the numbers from 1 .. n is n * (n + 1) / 2 (I'll leave the proof of that to you :))

Make sure you give me credit when you turn this in to your instructor :)

[TrustyTony]

I think OP meant general array not number range, which is trivial:

a sequence with n elements (n<=10^6)

[Momerath]

I think OP meant general array not number range, which is trivial:

Not sure what you are saying here. My solution works for any set of numbers. If they are ordered then the solution is trivial but since he seems to think it is O(n^2) then that would imply that they are not ordered.

[nezachem]

Not sure what you are saying here.

Neither do I. Where does SpecialSum() came from?

[TrustyTony]

This is what I refered:

A index 0   1   2   3   4   5   6   7   8   9   10
Value   23  4   65  2   34  12  43  1   3   5   99

i goes from 0 until 10, let's say the sum range is L=5 to R=35 

start index sums starting from index
0           23, 23+4=27, (27+65>R, break, count 2)
1           (4<L), (65+4>R, break, count 0)
2           (65>R, break, count 0)
3           (2<L), (2+34>R, break, count 0)
4           34, (34+12>R, break, count 1)
5           12, (43>R, break, count 1)
6           (43>R, break, count 0)
7           (1<L, 1+3=4<L,) 4+5=9, (99>R, break, count 1)
8           (3<L,) 3+5=8, (8+99>R, break, count 1)
9           (99>R, count 0)

Total 2+0+0+0+1+1+0+1+1+0=6

[JeffGrigg]

It occurs to me that if all the values are positive, then building a parallel array with a cumulative sum would be helpful:

/**
 * "A sequence Problem" as proposed on http://www.daniweb.com/software-development/computer-science/threads/375066
 */
public class ASequenceProblem {

	public static void main(String[] args) {
		int[] values = { 23, 4, 65, 2, 34, 12, 43, 1, 3, 5, 99 };
		int L = 5, R = 35;
		System.out.println("L=" + L + ", R=" + R);
		System.out.println();

		int[] sums = computeSums(values);

		int totalFound = 0;
		int jL = 1, jR = 0;
		for (int idx = 1; idx < sums.length - 1; ++idx) {
			int base = sums[idx - 1];
			while (sums[jL] - base < L)
				++jL;
			if (jR < jL)
				jR = jL;
			while (sums[jR] - base <= R)
				++jR;
			int numFound = jR - jL;
			if (numFound > 0)
				displayNumberFound(values, idx, jL, jR);
			totalFound += numFound;
		}

		System.out.println();
		System.out.println("Total found = " + totalFound);
	}

	private static int[] computeSums(int[] values) {
		int[] sums = new int[1 + values.length + 1];
		sums[0] = 0;
		for (int idx = 0; idx < values.length; ++idx)
			sums[idx + 1] = sums[idx] + values[idx];
		sums[sums.length - 1] = Integer.MAX_VALUE;
		return sums;
	}

	private static void displayNumberFound(int[] values, int idx, int jL, int jR) {
		int numFound = jR - jL;

		int i = idx - 1;
		System.out.println("Found " + numFound + " at i=" + i);
		for (int j = jL - 1; j < jR - 1; ++j) {
			StringBuilder sb = new StringBuilder();
			int localSum = 0;
			for (int sumIdx = i; sumIdx <= j; ++sumIdx) {
				int thisValue = values[sumIdx];
				if (sb.length() > 0)
					sb.append(" + ");
				sb.append(thisValue);
				localSum += thisValue;
			}
			System.out.println("  [" + i + ".." + j + "] " + sb.toString()
					+ " = " + localSum);
		}
	}

}

Output:

L=5, R=35

Found 2 at i=0
  [0..0] 23 = 23
  [0..1] 23 + 4 = 27
Found 1 at i=4
  [4..4] 34 = 34
Found 1 at i=5
  [5..5] 12 = 12
Found 1 at i=7
  [7..9] 1 + 3 + 5 = 9
Found 1 at i=8
  [8..9] 3 + 5 = 8
Found 1 at i=9
  [9..9] 5 = 5

Total found = 7

[TrustyTony]

Sorry, should have checked before posting, I left out the A[9].
Good point of positivity, for negative values, if they are included we should catch minimum value in first pass over the array and it could help or sum of continuous negative values.

I should have checked at least with simple non-scaling one liner like this:

# simplistic Python solution,
# must prepare optimized subsum instead of standard one to scale to 1000000 values
sequence = (23, 4, 65, 2,  34, 12, 43, 1, 3, 5, 99)
left, right = 5, 35
print(sum(1
          for start in range(len(sequence))
          for end in range(start, len(sequence)) 
          if left <= sum(sequence[start:end]) <= right))
""" Output
7
"""

[JeffGrigg]

P.S. In spite of the nested loops, I think I can show that my solution is "O(N)". I could do this by showing that ++jL; is executed at most N times. Same for ++jR; .

[TrustyTony]

JeffGrig:
I tried to add random integer generation (absolute values to keep them positive), but I get index error from the code:

C:\Tony>java ASequenceProblem > result1000.txt
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1002
        at ASequenceProblem.main(ASequenceProblem.java:25)

The beginning I changed like this:

import java.util.Random;
import java.lang.Math;

public class ASequenceProblem {

	public static void main(String[] args) {
        Random r = new Random();
        int[] values = new int[1000];
        for (int i = 0; i < values.length; i++) {
            values[i] = Math.abs(r.nextInt());
        }
		int L = values[0], R = values.length / 4 * values[0];
/* rest same */

[JeffGrigg]

Works sometimes. Add this line:

if (L > R)
			throw new IllegalArgumentException("Expecting L <= R.  L=" + L + " and R=" + R);

P.S. Actually...
This fixes the problem:

values[i] = Math.abs(r.nextInt(Integer.MAX_VALUE / 1001));

Turns out that r.nextInt() produces many numbers that are too large: We'd have to store the sum as long values if we want to use the full range of int values. The sums were silently rolling over into negative value territory, messing up the algorithm.

[TrustyTony]

I am not so fluent in Java to put much effort to experiment with it, did little more advanced version for only count, but it seems to explode at arround 10000 positive values with L=random element, R = quarter of sum of sequence + L. My simple code had also bug, the end of range at line 7 should be len(sequence)+1. I found the bug through difference in results with my little more advanced version of Python code:

from __future__ import print_function
import random
import time

def check_subsums(sequence, left, right):
    subsums = []
    for ind, s in enumerate(sequence):
        if s <= right:
            subsums.append((ind, s))
            if left <= s:
                yield 1
    for length in range(2, len(sequence) + 1):
        next_subsums = []
        for position, subsum in subsums:
            if position < len(sequence) - 1:
                value = sequence[position+1] + subsum
                if value < right:
                    next_subsums.append((position+1,value))
                if left <= value <= right:
                    yield 1
        if not next_subsums:
            break
        subsums = next_subsums

def simple_subsums(sequence, left, right):
    return sum(1
                for start in range(len(sequence))
                for end in range(start, len(sequence)+1)
                if left <= sum(sequence[start:end]) <= right)


n= 2000
huge = [random.randint(1, 100000) for count in range(n)]
left = random.choice(huge)
right = left + sum(huge)//4

print(n, left, right)
t0 = time.clock()
print('advanced')
print(sum(check_subsums(huge, left, right)), time.clock()-t0, 's')
t0 = time.clock()
print('simple')
print(simple_subsums(huge, left, right), time.clock()-t0, 's')

""" Example output:
2000 15975 25299462
advanced
863737 0.878409127417 s
simple
863737 34.9436213262 s

"""

[hqt]

for long time, i cannot connect to network, and I when I'm going here, I remember the problem I post that may I forgot. Sorry for all :)

to answer some things not clearly in the test: first, the sequence is not increasing or decreasing. second, this is very important: that the element can POSITIVE OR NEGATIVE.

this example will show you what important is that: 3 4 -100. R=6
we see that 3+4>6, but we cannot break here, because 3+4-100<6.

@pyTony: the last post of you, I haven't read it,yet because it's so long :">
but You had said this:

A index 0   1   2   3   4   5   6   7   8   9   10
Value   23  4   65  2   34  12  43  1   3   5   99

i goes from 0 until 10, let's say the sum range is L=5 to R=35 

start index sums starting from index
0           23, 23+4=27, (27+65>R, break, count 2)
1           (4<L), (65+4>R, break, count 0)
2           (65>R, break, count 0)
3           (2<L), (2+34>R, break, count 0)
4           34, (34+12>R, break, count 1)
5           12, (43>R, break, count 1)
6           (43>R, break, count 0)
7           (1<L, 1+3=4<L,) 4+5=9, (99>R, break, count 1)
8           (3<L,) 3+5=8, (8+99>R, break, count 1)
9           (99>R, count 0)

Total 2+0+0+0+1+1+0+1+1+0=6

this just true for positive integer. so I think your code is wrong. (sorry if I understand wrong or you had changed your code different with you explain). huh :)

[TrustyTony]

The simplistic double loop does not care if they are negative or positive, but it is quadratic like you said, also I have two alternatives for this case, which are recursive memoized sum and preprepared cumulative sums version (which seems fastest of these, but still goes over 4 s around 4000 items instead of 10000000.

from __future__ import print_function
import random
import time


def rsum(sequence, start, end):
    """ use cumulative sums and cached recursion to find the subsequence sums """
    if start >= end or not sequence:
        return 0
    elif not start:
        if end not in rsum.cache:
            rsum.cache[end] = rsum(sequence, start, end-1) + sequence[end-1]
        return rsum.cache[end]
    else:
        return rsum(sequence, 0, end) - rsum(sequence, 0, start)
rsum.cache = dict()

def number_of_subsums(sequence, start, end):
    return sum(1
                  for start in range(len(sequence))
                  for end in range(start, len(sequence)+1)
                  if left <= rsum(sequence, start, end) <= right)


def simple_subsums(sequence, left, right):
    return sum(1
                for start in range(len(sequence))
                for end in range(start, len(sequence)+1)
                if left <= sum(sequence[start:end]) <= right)


def cumulative_subsums(cumulative, left, right):
    return sum(1
                  for start in range(len(sequence))
                  for end in range(start, len(sequence)+1)
                  if left <= (cumulative[end] - cumulative[start]) <= right)

# sequence = 3, 4, -100
# item_count = len(sequence)
# left, right = -200, 4
# 20000 -> more than three minutes
item_count= 1000
sequence = [random.randint(-1000000, 100000) for count in range(item_count)]
left = random.choice(sequence)
right = left + sum(sequence)//4

if right < left:
    right, left = left, right

print('%i numbers left: %i, right: %i' %
      (item_count, left, right))

t0 = time.clock()
print('Prepare ready cumulative sums')

cumulative = [0]
for value in sequence:
    cumulative.append(cumulative[-1]+value)
s3 = cumulative_subsums(cumulative, left, right)
t0 -= time.clock()
print('Cumulative direct: %i numbers left: %i, right: %i, subsetsums: %s (%.3f s)' %
      (item_count, left, right, s3, -t0))

t0 = time.clock()
print('Recursive cached')
print(number_of_subsums(sequence, left, right), time.clock()-t0, 's')
t0 = time.clock()

t0 = time.clock()
print('simple')
print(simple_subsums(sequence, left, right), time.clock()-t0, 's')

I think that you should adapt this simple maximum sum algorithm to range case:
http://wordaligned.org/articles/the-maximum-subsequence-problem

Must find dynamic programming/cached recursive formula that can multiply numbers of solutions together to get number of combinations instead of counting them one by one.

I did not catch the Java algorithm so deeply, I should inspect it by recoding it in Python to understand it well. The poster did say that the code was limited to positive numbers.