Question: Question

> 
> Given an array of non negative integers `A`, and a range `(B, C)`, find the number of continuous subsequences in the array which have sum `S` in the range `[B, C]` or `B <= S <= C`
> 
> 
> Continuous subsequence is defined as all the numbers `A[i]`, `A[i + 1]`, .... `A[j]` where `0 <= i <= j < size(A)`
> 
> 
> Example :
> 
> 
> 
> ```
> A : [10, 5, 1, 0, 2]
> (B, C) : (6, 8)
> 
> ans = 3
> 
> ```
> 
> `[5, 1]`, `[5, 1, 0]`, `[5, 1, 0, 2]` are the only 3 continuous subsequence with their sum in the range `[6, 8]`
> 
> 
> 

My code

```
public int numRange(ArrayList<Integer> a, int b, int c) {

    int curr_sum = a.get(0), start = 0;
    int i = 0, count = 0;
    for (i = 1; i < a.size(); i++) {
        // If curr_sum exceeds the sum, then remove the starting elements
        while (curr_sum > c) {
            curr_sum = curr_sum - a.get(start);
            start++;
        }

        // If curr_sum becomes equal to sum, then return true
        if (b <= curr_sum && curr_sum <= c) {
            count++;
        }

        // Add this element to curr_sum
        if (i < a.size())
            curr_sum = curr_sum + a.get(i);

    }

    return count;
}

```

Problem : Wrong Answer.

What are the cases I am missing ?
How do I improve the efficiency of this code after rectifying it ?

Answer: 
```
public static int numRange(ArrayList<Integer> a, int b, int c) {
    int counter =0;
    int result =0;
    for(int i =0; i< a.size(); i++){
            result = a.get(i);
            if( result >= b && result <= c){
                counter++;
            }
            int k =i+1;
            while(k< a.size()){
                result = result+ a.get(k);
                if( result >= b && result <= c){
                    counter++;
                }
                else if( result >c){
                    break;
                }
                k++;
            }
    }
    return counter;
}

```
Your approach misses lots of subsequences. Suppose the input is `[1, 2, 3, 4, 5]`, and the interval is `(2, 9)`. Your algorithm counts `[1, 2]` and `[1, 2, 3]`. When it gets to `[1, 2, 3, 4]`, since the sum is too large, you then eliminate numbers from the beginning of the subsequence until the sum becomes within range. But how is this ever going to count `[2]`, `[2, 3]`, or `[3]`? At this point you're no longer counting subsequences that end with anything that comes before 4.

I don't know the answer. To use a basic (but probably too inefficient) method, you'll need to use a double loop to examine all subsequences. To make it efficient, you'll need to be cleverer. For example, if a subsequence `a[i] .. a[j]` has a sum that's <= `c`, then all smaller subsequences also have sums <= `c`, and you can compute the number of subsequences using simple algebra--but figuring out which of those also have sums >= `b` will be necessary too.