find the Contiguous Subarray with Sum to a Given Value in an array

Problem :

Given an array of positive integer and given value X, find Contiguous sub array whose sum is equal to X.
For example:
arr[]={14, 12, 70, 15, 99, 65, 21, 90}; 
X =97.
Sum found between index 1 to 3
Elements are 12, 17 and 15

Solution:

Solution 1: 

Check all sub arrays and if current sum is equal to X, return. This will require two loops and if currentSum is greater than X tben try another sub array.
Java code:
static void findSubArraySumEqualToX(int arr[], int X) {
  int currentSum;
  for (int i = 0; i < arr.length; i++) {
   currentSum = arr[i];
   // try all subarrays starting with 'i'
   for (int j = i + 1; j <= arr.length; j++) {
    if (currentSum == X) {
     int endIndexForContArray = j - 1;
     System.out.println("Sum found between indexes " + i + " and " + endIndexForContArray);
     for (int k = i; k <= endIndexForContArray; k++) {
      System.out.print(arr[k]+" ");
     }
     return;
    }
    if (currentSum > X || j == arr.length)
     break;
    currentSum = currentSum + arr[j];
   }
  }

  System.out.println("No subarray found");
  return;
 }
Time Complexity : O(N^2)

Solution 2: 

Lets say array is arr[] and given sum is X.
  • Iterate over array arr[]. 
  • If currentSum is less than X then add current element to currentSum.
  • If currentSum is greater than X , it means we need to remove starting elements to make currentSum less than X.
  • If CurrentSum is equal to X, we got the continuous sub array, print it.
Java Code:
 public static void findSubArraySumEqualToXOptimized(int arr[], int X) {
  int currentSum = arr[0];
  int start = 0;

  for (int i = 1; i <= arr.length; i++) {
   // If currentSum is more than the sum, start removing starting elements unless you get currentSum is less than X
   while (currentSum > X && start < i - 1) {
    currentSum = currentSum - arr[start];
    start++;
   }

   // If currentSum becomes equal to sum, then print the index
   if (currentSum == X) {
    int endIndexForContArray = i - 1;
    System.out.println("Sum found between indexes " + start + " and " + endIndexForContArray);
    System.out.println("Printing Array values : ");
    for (int j = start; j <= endIndexForContArray; j++) {
     System.out.print(arr[j]+" ");
    }
    return;
   }

   // Add this element to currentSum
   if (i < arr.length)
    currentSum = currentSum + arr[i];
  }
Time Complexity : O(N) 

Java program to find the Contiguous Subarray with Sum to a Given Value in an array :

package org.arpit.java2blog;

public class FindSumSubArrayMain {
 public static void main(String[] args) {

  int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };

     findSubArraySumEqualToX(arr, 33);
     System.out.println("\n======================");
  findSubArraySumEqualToXOptimized(arr, 33);
 }

 static void findSubArraySumEqualToX(int arr[], int X) {
  int currentSum;
  for (int i = 0; i < arr.length; i++) {
   currentSum = arr[i];
   // try all subarrays starting with 'i'
   for (int j = i + 1; j <= arr.length; j++) {
    if (currentSum == X) {
     int endIndexForContArray = j - 1;
     System.out.println("Sum found between indexes " + i + " and " + endIndexForContArray);
     for (int k = i; k <= endIndexForContArray; k++) {
      System.out.print(arr[k]+" ");
     }
     return;
    }
    if (currentSum > X || j == arr.length)
     break;
    currentSum = currentSum + arr[j];
   }
  }

  System.out.println("No subarray found");
  return;
 }

 public static void findSubArraySumEqualToXOptimized(int arr[], int X) {
  int currentSum = arr[0];
  int start = 0;

  for (int i = 1; i <= arr.length; i++) {
   // If currentSum is more than the sum, start removing starting elements unless you get currentSum is less than X
   while (currentSum > X && start < i - 1) {
    currentSum = currentSum - arr[start];
    start++;
   }

   // If currentSum becomes equal to sum, then print the index
   if (currentSum == X) {
    int endIndexForContArray = i - 1;
    System.out.println("Sum found between indexes " + start + " and " + endIndexForContArray);
    System.out.println("Printing Array values : ");
    for (int j = start; j <= endIndexForContArray; j++) {
     System.out.print(arr[j]+" ");
    }
    return;
   }

   // Add this element to currentSum
   if (i < arr.length)
    currentSum = currentSum + arr[i];
  }

 }

}
When you run above program , you will get below output:
Sum found between indexes 6 and 7
10 23 
======================
Sum found between indexes 6 and 7
Printing Array values : 
10 23 

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012