## Facebook Interview Question for Software Engineers

Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
12
of 16 vote

``````public boolean findSum (int [] A ,int T){
int sum = 0 ;
int j = 0;
for (int i = 0 ; i < A.length ; ++i) {
while (j < A.length &&  sum < T) {
sum += A[j] ;
j++;
}
if (sum == T) {
return true ;
}
sum -= A[i] ;
}

return false ;``````

}

Comment hidden because of low score. Click to expand.
0

public static boolean calc(int[] num, int target) {
int sum;
for (int i = 0; i < num.length; i++) {
sum = num[i];
for (int j = i + 1; j < num.length; j++) {
sum = sum + num[j];
if (sum == target) {
return true;
} else if (sum < target) {
continue;
} else {
break;
}
}
}

return false;
}

Comment hidden because of low score. Click to expand.
-2

This is wrong. What about this sequence (6, 3, 4, 10), 20. Going through the loop will pop 6 immediately. while the correct answer should be: (6,4, 10)

Comment hidden because of low score. Click to expand.
0

@Howard: We're only looking for continuous sequences.
@Chris: Are you sure that

``++i``

makes sense since you're substracting A[1] from sum after adding A[0] to it on first iteration if A[0] > N ? (check data from first example)

Comment hidden because of low score. Click to expand.
1
of 5 vote

Use Sliding Window to slides along the sequence, watching the sum of numbers inside the window:
If sum less than T: expand the window to the right;
If sum = T: report true, finish;
If sum > T: shrink the window from left.

EDIT:
This algorithm works for positive numbers.
It takes O(N) time, O(1) space, where N is the size of array.

Pseudo code (which is almost code!):

``````checkSum(){
wL = 0, wR = 0, sum = A[0]; // fixed by phantomlord, thanks!

while(wR<N){
if (sum < T){
wR++;			//expand to the right
sum += A[wR];	//update sum
};

if (sum==T) return true;

if (sum > T){
sum -= A[wL];	//update sum
wL++;			//shrink from left
};
};

return false;
}``````

EDIT2:
For input of both NEGATIVE and positive numbers: we can store cumulative sum at each position in a hash table and check for the sum of T along the way.

If we see Sum at current position i, and saw Sum-T at some previous position j, then all numbers between j and i will sum up to T.

Remember to check the case Sum-T = Sum. To avoid that case, need to check the hash table before inserting current Sum into it.

Still O(N) time, but O(N) space needed.

Credit to eugene.varovoi!

Pseudo code:

``````checkSum(){
Sum = 0;
HashSet = {};

for i = 0..N-1
Sum += A[i];
//if see a value of  (Sum-T) previously, report true, else insert current Sum in:
if HashSet contains (Sum-T) then return true;
else HashSet.insert(Sum);
};

return false;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

the array isn't sorted, won't work

Comment hidden because of low score. Click to expand.
0

The numbers were stated to be positive, this WILL work

Comment hidden because of low score. Click to expand.
0

I think this should work even with an unsorted array.

``````function find_sum(arr, target)
{
var sum = 0;
for (var idx_right =0, idx_left = 0; idx_right < arr.length; ++idx_right)
{
sum += arr[idx_right];
while (sum > target)
{
sum -= arr[idx_left];
++idx_left;
}
if (sum == target)
return true;
}
return false;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

This should work even without a sorted array.

``````function find_sum(arr, T)
{
var sum = 0;
for (var i =0, j = 0; i < arr.length; ++i)
{
sum += arr[i];
while (sum > T)
{
sum -= arr[j];
++j;
}
if (sum == T)
return true;
}
return false;
}``````

This runs in O(n) time and O(1) space.

Comment hidden because of low score. Click to expand.
1
of 1 vote

The problem statement only allowed for positive numbers, so this approach is correct. If negative numbers were also allowed, here's a different approach that works for all numbers.

Build a cumulative array where the i-th element contains the sum of the first i numbers. Then, scan through the cumulative array, and for each value v, check whether v-T has been previously seen in the cumulative array (to do this efficiently, use a hash table and add the elements of the cumulative array to it as you go).

Comment hidden because of low score. Click to expand.
0

@phantomlord: fixed first bug! Thanks!

Second bug: each time the window only moves at most 1 position, thus sum is checking at every position.

Comment hidden because of low score. Click to expand.
1
of 1 vote

@ninhnnsoc, OK, I realised the second comment was invalid after writing and deleted it.
There is one more bug. Feed the input [1, 3, 5, 23, 2], 7.
The sum is 2 at the last index because everything up to that point does not add up to 7. Because the sum is 2, it increments wR which goes over the bounds of the array and when accessing it to accumulate the next sum, the position is N, hence invalid. You'll probably need to return false if wR is == N after incrementing to prevent that.

Comment hidden because of low score. Click to expand.
0

@phantomlord: why don't you give real code and fix the bug for me :)
Thanks!

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````while (wR < nums.length) {
if (sum == target)
return true;
else if (sum > target) {
sum -= nums[wL++];
} else if (wR<nums.length-1){
sum += nums[++wR];
} else {
wR++;
}``````

}

should check if wR out of index when increase it and add it to sum

Comment hidden because of low score. Click to expand.
1
of 1 vote

@ninhnnsoc, here you go :-) Test cases included. Don't get me wrong, your solution is very neat, does the job in one loop. Hence a lot of scrutiny.

``````public class ContinuousSequenceSum {
public static boolean sumsTo(int[] a, int T) {
int wL = 0, wR = 0, sum = a[0];

while (wR < a.length) {
if (sum < T) {
if (wR < a.length-1) ++wR;
else                 return false;
sum += a[wR];
}

if (sum==T) return true;

if (sum > T) {
sum -= a[wL];
++wL;
}
}
return false;
}

public static void main(String[] args) {
int[] a1 = {23, 5, 4, 7, 2, 11};
int   t1 = 20;
System.out.println(sumsTo(a1, t1)); // true

int[] a2 = {1, 3, 5, 23, 2};
int   t2 = 8;
System.out.println(sumsTo(a2, t2)); // true

int[] a3 = {1, 3, 5, 23, 2};
int   t3 = 7;
System.out.println(sumsTo(a3, t3)); // false

int[] b1 = {23, 5, 12, 4, 7, 9};
int   u1 = 20;
System.out.println(sumsTo(b1, u1)); // true

int[] b2 = {1, 2, 23, 24, 20, 4, 7, 9};
int   u2 = 20;
System.out.println(sumsTo(b2, u2)); // true

int[] b3 = {25, 23, 24, 20, 4, 7, 9};
int   u3 = 20;
System.out.println(sumsTo(b3, u3)); // true

int[] b4 = {1, 2, 3, 4, 20, 21, 5, 9, 6};
int   u4 = 20;
System.out.println(sumsTo(b4, u4)); // true
}
}``````

Comment hidden because of low score. Click to expand.
0

@phantomlord: excellent! It works.
Can initiate A[n] = A[n+1] = 0, it also works.

Comment hidden because of low score. Click to expand.
0

You may be at at max possible valid wR, and then you just increment wR and read at it without checking for validity... so you may end up reading past the end of the array... Try it with array {1,1,1,100} and target sum 5.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi, Just wonder if this can handle [1,1,1,1,1,1,1] 20 case.
Correct me if I am wrong. This algorithm will go into infinite loop for this input since there is no boundary check for array.

Comment hidden because of low score. Click to expand.
1
of 1 vote

I think for worst case this would be O(N^2), not O(N). This is because if you have
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,99], 100, the first time you have to check n numbers, then the second you check n-1 numbers and essentially won't find a result until you hit the last two, which ends up being O(N^2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def findSub(self,A,target):
length = len(A)
i = 0
while(i<length-1):
output = target-A[i]
if output<0:
i+=1
elif output==0:

return True
break

else:
for j in range(i+1,length):
output =output-A[j]
if output <0:
i+=1
break
elif output==0:
return True
break
else:
output = output
return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
for(int i = 0; i<arr.length(); i++){
if(flag)
startIndex = i;

sum = sum + arr[i];
if(sum < T){
flag = false;
continue;
}
while(sum > T && startIndex <= i){
sum = sum - arr[startIndex];
startIndex++;
}
if(startIndex == i)
flag = true;

if(sum == T)
return true;
}
return false;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static bool IsSubsetSum(int T, int[] S)
{
for(int i = 0; i < S.Length; i++)
{
int total = 0;
for(int j = i; j < S.Length; j++)
{
total += S[j];
if(total == T)
{
return true;
}
}

return false;
}
}``````

Comment hidden because of low score. Click to expand.
0

Don't understand why everybody else assumes that the numbers are only positives.
You need to look at the entire array in order to determine if the SUM exist.

Comment hidden because of low score. Click to expand.
0

Oh finally saw it. Darn "only positive numbers".

Comment hidden because of low score. Click to expand.
1
of 1 vote

For negatives numbers, O(N) time solution exists!
See EDIT2 of my post and comment of eugene.varovoi

Comment hidden because of low score. Click to expand.
0

Thanks for the input.
Yep I just realized when I did it in the white board but I'll post it as a new entry.

Comment hidden because of low score. Click to expand.
0

Actually I saw that you use a HashSet I do not quite understood how it works.

I tried with a couple of samples and indeed does work but I'm still sort not sure how it does work.

Comment hidden because of low score. Click to expand.
0
of 0 vote

bool doesContSeqExists(int &vTargSum, vector<int> &vInput)
{
int vSum = 0;
int totalIterations = 0;
totalIterations = vInput.size();
int skipIterations=0;

for(int i=0;i<totalIterations;i++)
{

skipIterations = 0;
vSum = 0;
for(auto e:vInput)
{
if(skipIterations<i)
{
skipIterations++;
continue;
}

if(e == vTargSum)
{
return true;
}
else
{
vSum += e;
if(vSum>vTargSum)
{
vSum = 0;
continue;
}
else if(vSum == vTargSum)
{
return true;
}
}
}
}

return false;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Will your solution work dor this sequence and sum . 18 1 5 14 28 40. And target sum 20

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````bool hasContSeq(std::vector<int>& vec, int num)
{
int sum = 0;

for (int i = vec.size() - 1; i >= 0; --i)
{
if (sum == num)
{
return true;
}
else if (sum > num)
{
sum = vec[i];
}
else
{
sum += vec[i];
if (sum > num)
{
sum = vec[i];
}
}
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isSequence(int[] a, int val){
int start=0;
int sum=0;
int len = a.length;
for(int i=0;i++;i<len){
sum+=a[i];
if(sum == val){
return true;
}
else if(sum < val){
continue;
}else{
while (sum > val && start < len){
sum-=a[start];
start++;
}
if(sum == val){
return true;
}
}
}
return false;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python, O(n) time and O(1) extra space:

``````def hasSum(A,T):
if len(A) == 1:
return A[0] == T
elif len(A) == 0:
return False
left = 0
right = 1 # exclusive
total = A[0]
while True:
if total < T:
right += 1
if right == len(A):
break
total += A[right]
elif total > T:
left += 1
total -= A[left]
else:
return True
return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code

``````def sumT(A, T):
front = 0
rear  = 0

while front < len(A):

T = T - A[front]

# case 1
if T == 0:
return True

# case 2
elif T < 0:

# add rear index until positive
while T < 0:
T = T + A[rear]
if T == 0:
return True
rear += 1

# Now that T is just positive again, step front pointer forward
front += 1

# case 3
else: # T > 0
front += 1

return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Code
O(n), in place.

``````def sumT(A, T):
front = 0
rear  = 0

while front < len(A):

T = T - A[front]

# case 1
if T == 0:
return True

# case 2
elif T < 0:

# add rear index until positive
while T < 0:
T = T + A[rear]
if T == 0:
return True
rear += 1

# Now that T is just positive again, step front pointer forward
front += 1

# case 3
else: # T > 0
front += 1

return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````O(N) solution

public static boolean contSeq(int [] A, int T) {
int start = -1, end = -1, tempSum = 0;
int len = A.length;
for (int i=0; i<len; i++) {
tempSum += A[i];
start = start==-1?i:start;
end = i;

if (tempSum==T) {
System.out.println("Starting index: " + start + " Ending index: " + end);
return true;
}
else if (tempSum>T){
while (tempSum>T && start<=end) {
tempSum -= A[start++];
if (tempSum==T) {
System.out.println("Starting index: " + start + " Ending index: " + end);
return true;
}
}
}
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public boolean contSeq(int [] A, int T) {
int start = -1, end = -1, tempSum = 0;
int len = A.length;
for (int i=0; i<len; i++) {
tempSum += A[i];
start = start==-1?i:start;
end = i;

if (tempSum==T) {
System.out.println("Starting index: " + start + " Ending index: " + end);
return true;
}
else if (tempSum>T){
while (tempSum>T && start<=end) {
tempSum -= A[start++];
if (tempSum==T) {
System.out.println("Starting index: " + start + " Ending index: " + end);
return true;
}
}
}
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static boolean hasContSeq(int[] a, int T) {
int sum = 0;
int k = 0;
for (int j = 0; j < a.length; j++) {
if(a[j] > T){
k++;
sum=0;
continue;
}
sum += a[j];
while(sum > T){
sum -= a[k];
k++;
}
if(sum == T) return true;
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static boolean hasContSeq(int[] a, int T) {
int sum = 0;
int k = 0;
for (int j = 0; j < a.length; j++) {
if(a[j] > T){
k++;
sum=0;
continue;
}
sum += a[j];
while(sum > T){
sum -= a[k];
k++;
}
if(sum == T) return true;
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public boolean findSequenceSum (int [] a ,int T){
for(int i=0; i<a.length; i++) {
int sum = 0;
int j=i;
while (sum<T && j < a.length) {
sum += a[j];
j++;
}
if(sum==T)
return true;
}

return false;
}``````

``````public boolean findSequenceSum2(int[] a, int T){
int sum = 0;
int start = 0;
for(int i=0; i<a.length; i++) {
sum += a[i];
if(sum>T) {
while(sum >= T && start <= i) {
sum -= a[start];
start++;
if(sum==T)
return true;
}
} else {
if(sum==T)
return true;
}
}

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Test{
public boolean isSumSeq(int[] arr, int sum){
Queue<Integer> seqQ= new PriorityQueue<Integer>();
int currSum = 0;
for(int i : arr){
currSum += i;
if(currSum == sum)
return true;
if(currSum > sum){
while(currSum > sum){
int last = seqQ.pop();
currSum -= last;
}
}
if(currSum == sum)
return true;
}
return false;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

oh my friends , is it not the version of SUM OF SUBSET problem. whatever solutions you have submitted welldone!
but all the solutions will fail for the larger size of the problem.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Linear time taking care of negatives as well. I created a function that might as well return the subset as it knows the range but uses "yield return" so it return on the first part of the loop.

I used yield return if there is no need to find the actual values so it does not iterate through the results just tells if a result will exists on the first yield return.

``````public HasSubsetThatSums(int[] A, int T)
{

return (FindSubsetThatSums(A, T) != null);
}

public static IEnumerable<int> FindSubsetThatSums(int[] A, int T)
{
int tail = 0;
int sum = 0;

while(tail < A.Length)
{
if (sum > T)
{
}
else if ( sum < T)
{
sum += A[tail++];
}
else // if(sum == T)
{
for( int i = head; i < tail; i++)
{
yield return A[i];
}
}
}

return null;
}``````

Comment hidden because of low score. Click to expand.
0

How does it work for negative numbers?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public boolean isSum(int[] a, int t){

for(int i=0; i<=a.length; i++){
int j=i;
int sum = 0;
while(j<a.length){
if(a[j]>t) sum = 0;
sum += a[j];
if(sum>t) j++;
if(sum == t) return true;

j++;
System.out.println("Herej " + j);
//System.out.println("Herea " + a.length);
}

System.out.println("Here " + i);
}
return false;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def is_sumed(A, num):
s = 0
start_index = 0
i = 0
while i < len(A):
if s == 0:
start_index = i
s = s + A[i]
if s == num:
return True, start_index
if s > num:
s = 0
i = start_index + 1
else:
i = i + 1
return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static boolean isPossible(int a[], int index, int sum, int reqSum)
{
if(sum > reqSum)
return false;
if(index < 0)
return false;
if(sum == reqSum)
return true;
return isPossible(a, index -1, sum + a[index], reqSum) || isPossible(a, index-1, 0, reqSum);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def continuousArray(seq,num):
prevCount=0
nextCount=0
tSum=0
if len(seq)>0:
tSum=seq[prevCount]
while (prevCount<len(seq) ) and (nextCount<len(seq)):
if tSum <num:
nextCount= nextCount+1
if nextCount < len(seq):
tSum=tSum+seq[nextCount]
if tSum >num:
tSum=tSum-seq[prevCount]
prevCount=prevCount+1
if num==tSum:
return True
return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def continuousArray(seq,num):
prevCount=0
nextCount=0
tSum=0
if len(seq)>0:
tSum=seq[prevCount]
while (prevCount<len(seq) ) and (nextCount<len(seq)):
if tSum <num:
nextCount= nextCount+1
if nextCount < len(seq):
tSum=tSum+seq[nextCount]
if tSum >num:
tSum=tSum-seq[prevCount]
prevCount=prevCount+1
if num==tSum:
return True
return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def continuousArray(seq,num):
prevCount=0
nextCount=0
tSum=0
if len(seq)>0:
tSum=seq[prevCount]
while (prevCount<len(seq) ) and (nextCount<len(seq)):
if tSum <num:
nextCount= nextCount+1
if nextCount < len(seq):
tSum=tSum+seq[nextCount]
if tSum >num:
tSum=tSum-seq[prevCount]
prevCount=prevCount+1
if num==tSum:
return True
return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{ #include <iostream>
#include <vector>

using namespace std;

bool sumExists(vector<int>& a, int target) {
int n = a.size();
if (n == 0) return false;
if (a[0] == target) return true;
int s = 0;
int sum = a[0];
int i = 1;
while(i < n) {
if (sum + a[i] < target){
sum += a[i];
i++;
} else if (sum + a[i] > target) {
sum -= a[s];
s++;
} else {
return true;
}
}
return false;
}

int main() {
vector<int> a = {23,5,4,7,2,11};
cout << "sum exists : " << sumExists(a,20) << "\n";
cout << "sum exists : " << sumExists(a,28) << "\n";
cout << "sum exists : " << sumExists(a,11) << "\n";
cout << "sum exists : " << sumExists(a,190) << "\n";
cout << "sum exists : " << sumExists(a,23) << "\n";
a = {1,2};
cout << "sum exists : " << sumExists(a,3) << "\n";
} }}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static boolean consecutiveSum() {
int [] a = { 23,5,4,7,2,11};
int T = 11;
int sum = a[0];

for(int i = 0;i<a.length+1;){
if(sum < T){
sum+=a[i];
i++;
}
if(sum==T)
{
System.out.println(queue.toString());
return true;

}
if(sum >T){
sum-=queue.poll();
}

}

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Another Java version using a loop:

``````private static boolean sumLoop(int[] arr, int target) {
for (int sum = 0, i = 0, j = 0;;) {
if (sum == target) {
return true;
}

if (sum < target && i < arr.length) {
sum += arr[i++];
} else if (sum > target && j < arr.length) {
sum -= arr[j++];
} else {
return false;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution in PHP:

``````function sums(\$sequence, \$sum)
{
\$sequence_length = count (\$sequence);
foreach (\$sequence as \$key => \$value) {
\$count = 0;
for (\$i = \$key; \$i < \$sequence_length; ++\$i) {
\$count += \$sequence[\$i];
if (\$count == \$sum)
return true;
elseif (\$count > \$sum)
break;
}
}
return false;
}``````

To call and test the above function:

``````\$input = array (
array (array (23, 5, 4, 7, 2, 11), 20),
array (array (1, 3, 5, 23, 2), 8),
array (array (1, 3, 5, 23, 2), 7)
);

foreach (\$input as &\$row)
echo implode(',', \$row[0]) . " ... {\$row[1]} = " . (sums (\$row[0], \$row[1]) ? 'true' : 'false') . "\n";``````

This outputs:

``````23,5,4,7,2,11 ... 20 = true
1,3,5,23,2 ... 8 = true
1,3,5,23,2 ... 7 = false``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Folks ... my solution works irrespective of whether you have positive or negative number.

``````public static void main(String [] args) {

int a[] = new int[] {1,-3,5,23,28,2,3,7};
int b= 8,i=0;

int Sum=0 ;

while(Sum !=b  && (i!=a.length) ){

if (a[i] < b) {
Sum=Sum+a[i];
}
else {
Sum=0;
}
i++;
}
if (Sum==b) {
System.out.println(" we have found a match");
}
else {
System.out.println(" we have not  found a match");
}
-- INSERT --``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

below is my solution which works for both positive and negative number .rather adding to achieve the SUM ,my approach is to subtract and achieve 0, I have outer while loop on the list of array which will be incremented when we see negative number,value greater that SUM expected or the SUM computed greater than SUM expected.

``````class consArray {

public static void main(String []args) {

int [] a1 = {1,3,5,7,2};
int T =8;
int sum=T;
int i=0,j=0;
boolean cons=false;
while(i!=a1.length){
for ( j=i;j< a1.length;j++) {

if(sum==0){
cons=true;
break;
}
else {
if((a1[j]> T) || (sum<0)||(a1[j]<0)){
break;
}
else {
sum-=a1[j];
}
}
}
if(sum==0){
cons=true;
break;
}
sum=T;
i++;
}
if(cons)
System.out.println("We have consecutive sequence");
else
System.out.println("we dont have consecutive sequence");

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

test

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ version of solution with running time O(N), where N is the length of input array

``````#include <iostream>

using namespace std;

bool find_sum_seq(int* input, int target, int len)
{
int sum = 0, start = 0;
for (int i = 0; i <len; i++)
{
sum+= input[i];
if (sum == target)
break;
else if (sum > target)
{
while(start < len && start <= i && sum > target)
{
sum -= input[start++];
}
if (sum == target)
break;
}
}
return sum == target;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````boolean hasContSum(int[] in, int t) {
int lastStart, sum  = 0;
for (int i = 0; i < in.length; ) {
sum += in[i];
if (sum == t) {
return true;
} else if (sum > t) {
i = ++lastStart;
} else {
i++;
}
}

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple sliding window will do the trick

``````static int[] vals = {23, 5, 4, 7, 2, 11};
static int target =  18;
static void findConsecutiveSum()
{
int i = 0; int j =1;
int l = vals.length;
int targ = vals[0];
while(i < l && j < l)
{
if(targ == target){
System.out.println("from index "+i+"  to "+(j-1));
return;
}

if(targ < target)
{
targ = targ+vals[j];
j++;
}

if(targ > target)
{
targ = targ - vals[i];
i++;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>

using namespace std;

void ContinuousSequence(int *sequence, int length, int sum)
{
bool flag = false;

if (!sequence || length < 0)
return;

int curSum = sequence[0], start = 0, end, i;

for (i = 1; i <= length; i++)
{
while (curSum  > sum && start < i - 1)
{
curSum -= sequence[start];
start++;
}
if (curSum == sum)
{
flag = true;
end = i - 1;
}
if (i< length)
curSum += sequence[i];
}

if (flag)
{
cout << "\nThere is a Continuous Sequence to targeted Sum" << endl;

for (int i = start; i <= end; i++)
cout << sequence[i] << endl;
}

else
cout << "\nThere is no Continuous Sequence to targeted Sum" << endl;

cout << endl;
}

int main()
{
int sequence[] = { 23, 5, 4, 7, 2, 11 };
int length = sizeof(sequence) / sizeof(sequence[0]);
ContinuousSequence(sequence, length, 20);``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

# Here is my python solution
def is_continous_sum(A,T):
s = 0
n = len(A)
curr_sum = 0
for e in range(n):
curr_sum += A[e]
while curr_sum > T:
curr_sum -= A[s]
s+=1
if curr_sum == T:
return 1
return 0

Comment hidden because of low score. Click to expand.
0
of 0 vote

keep calculating currentSum until :
1. Either currentSum = desired sum
2. or if currentSum > desired sum , reset currentSum= value of current element(i.e we are starting out check sub-sequence from here)
3. or if currentSum < desired sum , keep adding next element

``````public class FindSumContinousArray {

public static void findContinuousSubArray(int[] arr , int sum){

int iCuurent=0;
int jCurrent=0;
int curSum=0;

while(iCuurent <= arr.length-1 && jCurrent <= arr.length-1){

curSum = curSum + arr[jCurrent]; // find new sum including current element
if(curSum == sum){
System.out.println("Sum found from elemen : " + iCuurent +" " +jCurrent);
return;
}else if(curSum > sum){
iCuurent = jCurrent; // start from current element new sum
curSum = arr[jCurrent];
jCurrent++;
}else{ // continue to include next element
jCurrent++;
}
}
}

public static void main(String[] args) {

int[] arr = {1,3,5,2,4};
findContinuousSubArray(arr,6);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

In 10 line of python, here you go.

``````def summed(seq, target):
current_sum = 0
for i in range(len(seq)):
current_sum  = current_sum + seq[i]
if current_sum == target:
return True
if current_sum > target:
current_sum = 0
return False
print summed([23, 6, 4, 8, 2, 2,], 22)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Since partial sums S[] make a sorted array we can use binary search to find whether there is a value that matches target, e.g. equals to S[k] + T, where k is the start index. We need to precompute partials sums.

This algorithms has O(n log n) time complexity worst case and O(n) space complexity.

``````boolean search(int[] A, int T) {
int n = A.length();

// S[i] = sum_{k < i} A[k]
//
// Hence,
// sum_{i <= k < j} A[k] == S[j] - S[i]
//
// E.g.:
// S[0] = 0
// S[1] = A[0]
// ...
// S[n] = A[0] + A[1] + ... + A[n-1]
int[] S = computePartialSums();

for (int i = 0; i < n; i += 1) {
boolean found = binarySearch(S, i + 1, n + 1, T + S[i]);

if (found) {
// sum_{i <= k < j} A[k] == T
return true;
}
}

return false;
}

// fromIndex inclusive
// toIndex exclusive
boolean binarySearch(int[] a, int fromIndex, int toIndex, int searchValue) {
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

A recursive approach:

``````fun hasContinuousSequence(array: IntArray, sum: Int, startedSoustracting: Boolean = false): Boolean {
if (array.isEmpty()) {
return sum == 0
}
if (sum == 0) {
return true
}

val first = if (sum - array.first() >= 0) {
hasContinuousSequence(array.drop(1).toIntArray(), sum - array.first(), true)
} else {
false
}
val second = if (!startedSoustracting) {
hasContinuousSequence(array.drop(1).toIntArray(), sum, startedSoustracting)
} else {
false
}

return first || second
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````private static boolean hasContinuousSequence(int[] arr, int t) {
if(arr == null) {
return false;
}

int sum = 0;

for(int i = arr.length - 1; i >= 0; i--) {
if(sum == t) {
return true;
} else if(sum > t) {
sum = arr[i];
} else {
sum += arr[i];
}
}

return false;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote
bool doesContSeqExists(int &vTargSum, vector<int> &vInput) {{{ int vSum = 0; int totalIterations = 0; totalIterations = vInput.size(); int skipIterations=0; for(int i=0;i<totalIterations;i++) {{{ skipIterations = 0; vSum = 0; for(auto e:vInput) {{{ if(skipIterations<i) {{{ skipIterations++; continue; }}} if(e == vTargSum) {{{ return true; }}} else {{{ vSum += e; if(vSum>vTargSum) {{{ vSum = 0; continue; }}} else if(vSum == vTargSum) {{{ return true; }}} }}} }}} }}} return false; }}}
Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````private static boolean hasContinuousSequence(int[] arr, int t) {
if(arr == null) {
return false;
}

int sum = 0;

for(int i = arr.length - 1; i >= 0; i--) {
if(sum == t) {
return true;
} else if(sum > t) {
sum = arr[i];
} else {
sum += arr[i];
}
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0

I don't see how this works.

Comment hidden because of low score. Click to expand.
0

You got the right idea but if (sum > i ) sum = arr[i]; section I don't think that is the right approach is better to subtract the first added value and so on.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.