CareerCup

Use two pointers, O(n) time complexity, O(1) space:

////assume target is positive
public boolean hasContSum(List<Integer> list, int target)
{
	int tail = 0;
	int sum = 0;
	for(int i=0;i<list.size();i++)
	{
		sum+=list.get(i);
		while(sum>target){ 
			sum-=list.get(tail++);
		}
        if(sum == target) return true;
	}
	return false;	
}

bool HasSumSubarray(vector<int> const &a, int n)
{
	int sum = 0;
	int start = 0;
	for (int i = 0; i < a.size(); ++i) {
		sum += a[i];
		while (sum > n &&
			start <= i)
		{
			sum -= a[start++];
		}
		if (sum == n) {
			return true;
		}
	}
	return false;
}

Can the list contain negative numbers?

func solve(array: [Int], input: Int) -> Bool {
    var left = input
    
    for element in array {
        left -= element
        
        if left == 0 {
            return true
        } else if (left < 0) {
            left = input - element
            continue
        }
    }
    
    return false
}

private static boolean sumCon(int[] list,int target){
int sum=0,position=0;

for(int i=0;i<list.length;i++){
sum+=list[i];

if(sum==target){
return true;
}

while(sum>target){
sum-=list[position];
position++;
}
}
return false;
}

private static boolean sumCon(int[] list,int target){
    int sum=0,position=0;
    
    for(int i=0;i<list.length;i++){
      sum+=list[i];
      
      if(sum==target){
        return true;
      }
      
      while(sum>target){
          sum-=list[position];
          position++;
      }
    }
    return false;
  }

private static boolean sumCon(int[] list,int target){
    int sum=0,position=0;
    
    for(int i=0;i<list.length;i++){
      sum+=list[i];
      
      if(sum==target){
        return true;
      }
      
      while(sum>target){
          sum-=list[position];
          position++;
      }
    }
    return false;
  }

Test:
list: [8,10,2,3,1,4,4] target = -10

Gives all possible solutions with complexity of O(n2)

public class ContElemSum {

    public static void main(String[] args) {

        Integer[] array = {6, 5, 3, 2, 1, 7};

        Integer targetValue = 10;

        for (int i = 0; i < array.length; i++) {
            Integer sum = array[i];
            List<Integer> result = new ArrayList<Integer>();
            result.add(array[i]);
            for (int j = i + 1; sum < targetValue && j < array.length; j++) {
                sum += array[j];
                result.add(array[j]);
            }
            if (sum == targetValue) {
                result.forEach(x -> System.out.print(x + " "));
                System.out.println();
            }
        }
    }
}

def main():
	input_list = [6, 5, 3, 2, 1, 7]
	number = int(input("accept number"))
	len_list = len(input_list) - 1

	total = 0
	l = []
	j = 0
	for i in range(len_list):
		j = i + 1
		total = sum(input_list[i: j + 1])
		if total == number:
			print("{0}===>{1}".format(total, input_list[i: j + 1]))
		if total < number:
			k = j + 1
			total += sum(input_list[k:k + 1])
			if total == number:
				print("{0}===>{1}".format(total, input_list[i: k + 1]))


if __name__ == '__main__':
	main()

O(n^2) brute force solution:

int adjacent(int list[], int length, int number)
{
  for(int i = 0; i < length; i++){
    int helper = 0;
    for(int j = 0; j < length; j++){
      helper = helper + list[i+j];
      if( helper == number) {
        return 1;
      }
    }
  }
  return 0;
}

int main(void)
{
  int list[] = {6, 3, 5, 3, 2, 22, 3, 4, 100, 6, 7, 10, 11};

  int length = sizeof(list)/sizeof(*list);
  printf("\n%d\n", adjacent(list,length, 31));

  return 0;
}

All solutions assume positive numbers. Here a solution with o(n^2) time, o(n) space, not assuming this. Working with negative numbers

def sum_find(x, s):
    if x[0] == s:
        return x[0]
    cumsum = [x[0]]*len(x)
    for end in range(1,len(cumsum)):
        cumsum[end] = cumsum[end-1] + x[end]
        if cumsum[end] == s:
            return x[:end+1]
        for start in range(end):
            if cumsum[end] - cumsum[start] == s:
                return x[start+1:end+1]
    return -1

x = [2,-3,5,1,-4,6,7,5,7,3,2,2,5,7,8,4,-2,-7,-2,5,3,-2,7,3,10,9,43]
sum_find(x, 11)

public void ContiguousElementsEqualToSum(int [] input, int sum)
        {
            int currentSum = 0;
            int currentIndex = 0;
            int lastIndex = 0;
            while (currentIndex < input.Length)
            {
                if(currentSum < sum || currentIndex == 0)
                {
                    currentSum += input[currentIndex];
                }
                while (currentSum >= sum)
                {
                    // Keep removing the first one.

                    if (currentSum == sum)
                    {
                        for (int i = lastIndex; i <= currentIndex; i++)
                        {
                            Console.Write("{0} ", input[i]);
                        }
                        Console.WriteLine();
                    }
                    currentSum -= input[lastIndex];
                    lastIndex++;
                }
                
                currentIndex++;
            }

public void ContiguousElementsEqualToSum(int [] input, int sum)
        {
            int currentSum = 0;
            int currentIndex = 0;
            int lastIndex = 0;
            while (currentIndex < input.Length)
            {
                if(currentSum < sum || currentIndex == 0)
                {
                    currentSum += input[currentIndex];
                }
                while (currentSum >= sum)
                {
                    // Keep removing the first one.

                    if (currentSum == sum)
                    {
                        for (int i = lastIndex; i <= currentIndex; i++)
                        {
                            Console.Write("{0} ", input[i]);
                        }
                        Console.WriteLine();
                    }
                    currentSum -= input[lastIndex];
                    lastIndex++;
                }
                
                currentIndex++;
            }

For given set above, if n is 10 shouldn't we return {5, 3, 2} instead of {2, 1, 7}?

public List find(int[] nums, int n) {
        int sum = 0;
        int start = 0;
        int end = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum == n) {
                end = i;
                List<Integer> result = new ArrayList<>();
                for (int j = start; j <= end; j++) {
                    result.add(nums[j]);
                }
                return result;
            } else if (sum > n) {
                sum = nums[i];
                start = i;
            }
        }
        return null;
    }

Shouldn't it return {5, 3, 2} if n is 10? This could be done as O(n)

public List getContiguousSum(int[] nums, int n) {
    List<Integer> result = new ArrayList<>();
    int sum = 0;
    int start = 0;
    int end = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (sum == n) {
            end = i;
            for (int j = start; j <= end; j++) {
                result.add(nums[j]);
            }
        } else if (sum > n) {
            sum = nums[i];
            start = i;
        }
    }
    return result;
}

Shouldn't it return {5, 3, 2} if n is 10? This could be done as O(n)

public List getContiguousSum(int[] nums, int n) {
    List<Integer> result = new ArrayList<>();
    int sum = 0;
    int start = 0;
    int end = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (sum == n) {
            end = i;
            for (int j = start; j <= end; j++) {
                result.add(nums[j]);
            }
        } else if (sum > n) {
            sum = nums[i];
            start = i;
        }
    }
    return result;

}

Shouldn't it return {5, 3, 2} if n is 10? This could be done as O(n)

public List getContiguousSum(int[] nums, int n) {
    List<Integer> result = new ArrayList<>();
    int sum = 0;
    int start = 0;
    int end = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (sum == n) {
            end = i;
            for (int j = start; j <= end; j++) {
                result.add(nums[j]);
            }
        } else if (sum > n) {
            sum = nums[i];
            start = i;
        }
    }
    return result;
}

O(n) solution

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int findMaxSubArraySum(int arr[], int n, int sum)
{
  int curr_sum = arr[0], max_sum = 0, start = 0;

  for(int i = 1; i < n; i++){

    // If curr_sum becomes greater than sum subtract starting elements of array
    while( curr_sum > sum && start < i) {
      curr_sum -= arr[start];
      start++;
    }

    max_sum = fmax(max_sum, curr_sum);

    curr_sum += arr[i];
  }

  if (curr_sum <= sum)
    max_sum = fmax(max_sum, curr_sum);

  if(max_sum == sum)
    return 1;
  else
    return 0;

}


int main(int argc, char **argv)
{
  int list[] = {6, 3, 5, 3, 2, 22, 3, 4, 100, 6, 7, 10, 11};

  int n = sizeof(list)/sizeof(*list);

  int sum = atoi(argv[1]);

  printf("\n%d\n",findMaxSubArraySum(list, n, sum));

  return 0;
}

#include <stdio.h>
#include <stdlib.h>

void print_sub_array(int *arr, int start_index, int end_index)
{
  while(start_index <= end_index) {
    printf("%d ", arr[start_index++]);
  }
  printf("\n");

  return;
}

void find_contiguous_elements_sum(int *arr, int num_elements, int sum)
{
  int start_index = 0, end_index = 0;
  int running_sum = 0;
  int i = 0;

  for(i = 0; i < num_elements; i++) {
    running_sum += arr[i];

    if (running_sum > sum) {
      /* discard elements from the start_index till running_sum < sum */
      while(running_sum > sum) {
        running_sum -= arr[start_index];
        start_index++;
      }
    }

    if (running_sum == sum) {
      print_sub_array(arr, start_index, (end_index = i));
      /* Continue finding next series */
      running_sum -= arr[start_index];
      start_index++;
    }

  }

  return;
}

int main(int argc, char *argv[])
{
  int arr[6] = {6,5,3,2,1,7};
  find_contiguous_elements_sum(&arr[0], 6, 8);
  find_contiguous_elements_sum(&arr[0], 6, 10);
  exit(0);
}

*** OUTPUT ***

$$  ./a.out 
5 3
1 7
5 3 2
2 1 7
$$

#include <stdio.h>
#include <stdlib.h>

void print_sub_array(int *arr, int start_index, int end_index)
{
  while(start_index <= end_index) {
    printf("%d ", arr[start_index++]);
  }
  printf("\n");
    
  return;
}
void find_contiguous_elements_sum(int *arr, int num_elements, int sum)
{
  int start_index = 0, end_index = 0;
  int running_sum = 0;
  int i = 0;
  
  
  for(i = 0; i < num_elements; i++) {
    running_sum += arr[i];
  
    if (running_sum > sum) {
      /* discard elements from the start_index till running_sum < sum */
      while(running_sum > sum) {
	running_sum -= arr[start_index];
	start_index++;
      }
    }

    if (running_sum == sum) {
      print_sub_array(arr, start_index, (end_index = i));
      /* Continue finding next series */
      running_sum -= arr[start_index];
      start_index++;
    }
    
  }
  
  return;
}

int main(int argc, char *argv[])
{
  int arr[6] = {6,5,3,2,1,7};
  find_contiguous_elements_sum(&arr[0], 6, 8);
  find_contiguous_elements_sum(&arr[0], 6, 10);
  exit(0);
}

*** OUTPUT ***
cup-questions$ ./a.out 
5 3 
1 7 
5 3 2 
2 1 7

#include <stdio.h>
#include <stdlib.h>

void print_sub_array(int *arr, int start_index, int end_index)
{
  while(start_index <= end_index) {
    printf("%d ", arr[start_index++]);
  }
  printf("\n");
    
  return;
}
void find_contiguous_elements_sum(int *arr, int num_elements, int sum)
{
  int start_index = 0, end_index = 0;
  int running_sum = 0;
  int i = 0;
  
  
  for(i = 0; i < num_elements; i++) {
    running_sum += arr[i];
  
    if (running_sum > sum) {
      /* discard elements from the start_index till running_sum < sum */
      while(running_sum > sum) {
	running_sum -= arr[start_index];
	start_index++;
      }
    }

    if (running_sum == sum) {
      print_sub_array(arr, start_index, (end_index = i));
      /* Continue finding next series */
      running_sum -= arr[start_index];
      start_index++;
    }
    
  }
  
  return;
}

int main(int argc, char *argv[])
{
  int arr[6] = {6,5,3,2,1,7};
  find_contiguous_elements_sum(&arr[0], 6, 8);
  find_contiguous_elements_sum(&arr[0], 6, 10);
  exit(0);
}
cup-questions$ ./a.out 
5 3 
1 7 
5 3 2 
2 1 7 
cup-questions$

#include <stdio.h>
#include <stdlib.h>

void print_sub_array(int *arr, int start_index, int end_index)
{
  while(start_index <= end_index) {
    printf("%d ", arr[start_index++]);
  }
  printf("\n");
    
  return;
}
void find_contiguous_elements_sum(int *arr, int num_elements, int sum)
{
  int start_index = 0, end_index = 0;
  int running_sum = 0;
  int i = 0;
  
  
  for(i = 0; i < num_elements; i++) {
    running_sum += arr[i];
  
    if (running_sum > sum) {
      /* discard elements from the start_index till running_sum < sum */
      while(running_sum > sum) {
	running_sum -= arr[start_index];
	start_index++;
      }
    }

    if (running_sum == sum) {
      print_sub_array(arr, start_index, (end_index = i));
      /* Continue finding next series */
      running_sum -= arr[start_index];
      start_index++;
    }
    
  }
  
  return;
}

int main(int argc, char *argv[])
{
  int arr[6] = {6,5,3,2,1,7};
  find_contiguous_elements_sum(&arr[0], 6, 8);
  find_contiguous_elements_sum(&arr[0], 6, 10);
  exit(0);
}

---

#include <stdio.h>
#include <stdlib.h>

void print_sub_array(int *arr, int start_index, int end_index)
{
  while(start_index <= end_index) {
    printf("%d ", arr[start_index++]);
  }
  printf("\n");
    
  return;
}
void find_contiguous_elements_sum(int *arr, int num_elements, int sum)
{
  int start_index = 0, end_index = 0;
  int running_sum = 0;
  int i = 0;
  
  
  for(i = 0; i < num_elements; i++) {
    running_sum += arr[i];
  
    if (running_sum > sum) {
      /* discard elements from the start_index till running_sum < sum */
      while(running_sum > sum) {
	running_sum -= arr[start_index];
	start_index++;
      }
    }

    if (running_sum == sum) {
      print_sub_array(arr, start_index, (end_index = i));
      /* Continue finding next series */
      running_sum -= arr[start_index];
      start_index++;
    }
    
  }
  
  return;
}

int main(int argc, char *argv[])
{
  int arr[6] = {6,5,3,2,1,7};
  find_contiguous_elements_sum(&arr[0], 6, 8);
  find_contiguous_elements_sum(&arr[0], 6, 10);
  exit(0);
}

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class ExistsSubarraySum {
   public static void main(String[] args){
	   int[] testcase1 = {6,5,3,2,1,7};
	   
	   boolean actual = existsSubarraySum(testcase1, 8);
	   System.out.println("test1 : target 8 " + actual);
	   
	   actual = existsSubarraySum(testcase1, 10);
	   System.out.println("test1 : target 10 " + actual);
	   
	   int[] testcase2 = {-6,2,3,-2,4,1,-5,6};
	   actual = existsSubarraySum(testcase2, 7);
	   System.out.println("test2 : target 7 " + actual);
   }
   
   public static boolean existsSubarraySum(int[] a, int target){
	   // if all elements are non negative, use specialized solution, O(n) time 
	   boolean allElementsAreNonNegative = true;
	   for (int e : a){
		   if (e < 0) {
			   allElementsAreNonNegative = false;
			   break;
		   }
	   }
	   if (allElementsAreNonNegative) {
		   return existsSubarraySumNonNegativeElements(a,target);
	   } else {
		   // else -- has negative elements
		   return existsSubarraySumGeneric(a,target);
	   }
   }
   
   public static boolean existsSubarraySumNonNegativeElements(int[] a, int target){
	   int n = a.length;
	   int start = 0, sum = 0;
	   for (int i = 0; i < n; i++){
		   sum = sum + a[i];
		   if (sum == target) {
			   return true;
		   } else if (sum > target) {
			   while (sum > target) {
				   sum = sum - a[start];
				   start++;
			   }
		   }
	   }
	   return false;
   }
   
   /**
    * 1) Compute prefix sums S
    * 2) for each i check if S(i) + target present 
    */
   public static boolean existsSubarraySumGeneric(int[] a, int target){
	   int n = a.length;
	   int[] prefixSum = new int[n];
	   
	   Map<Integer, Set<Integer>> sumVsPrefixIndex = new HashMap<Integer, Set<Integer>>();
	   for (int i = 0; i < n; i++){
		   prefixSum[i] = ((i > 0) ? prefixSum[i-1] : 0) + a[i];
		   
		   Set<Integer> values =  (sumVsPrefixIndex.containsKey(prefixSum[i])) ? 
				   sumVsPrefixIndex.get(prefixSum[i]) : new HashSet<Integer>();
		
		   values.add(i);
		   sumVsPrefixIndex.put(prefixSum[i], values);
	   }
	   
	   for (int i = 0; i < n; i++){
		   if (sumVsPrefixIndex.containsKey(prefixSum[i] + target)){
			   return true;
		   }
		   
		   Set<Integer> values = sumVsPrefixIndex.get(prefixSum[i]);
		   values.remove(i);
		   if (values.size() == 0){
			   sumVsPrefixIndex.remove(prefixSum[i]);
		   }
	   }
	   
	   return false;
   }
}