Number of contiguous subarrays within a sum range

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 ?

[1,1,1,1,1], b=1, c=5, answer is 15 - all possible subsequences. — user3707125
– user3707125, Commented Jan 1, 2016 at 20:04
with these inputsA : [ 80, 97, 78, 45, 23, 38, 38, 93, 83, 16, 91, 69, 18, 82, 60, 50, 61, 70, 15, 6, 52, 90 ] B : 99 C : 269 My answer is 20 and actual answer is 58 — Hacker8Heart
– Hacker8Heart, Commented Jan 1, 2016 at 20:14
To find all sub-sequences you can use algorithm that returns all combinations of two elements of the array. You just only need to sum elements in between. — Roman C
– Roman C, Commented Jan 1, 2016 at 20:28

Vinay K L · Accepted Answer · 2016-03-17 01:02:42Z

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; }

ajb · Accepted Answer · 2016-01-01 20:14:09Z

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.

Collectives™ on Stack Overflow

Number of contiguous subarrays within a sum range

2 Answers 2

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Related