How do you find continuous sub array whose sum is equal to a given number?

 How do you find continuous sub array whose sum is equal to a given number?

Problem :

You have given an integer array and a number. You need to find the continuous sub array of the given array whose sum is equal to given number. For example, If {12, 5, 31, 9, 21, 8} is the given array and 45 is the given number, then you have to find continuous sub array in this array such that whose elements add up to 45. In this case, {5, 31, 9} is such sub array whose elements add up to 45.

Logic Used To Find Continuous Sub Array Of An Array Whose Sum Is Equal To Given Number :

Let inputArray be the given integer array and inputNumber be the given number. First we initialize the sum to first element of the inputArray. Starting from the second element, we go on adding each element of inputArray to sum one by one. If the sum exceeds the inputNumber then we remove starting elements from the sum until sum becomes either smaller than the inputNumber or equal to inputNumber. If sum becomes equal to inputNumber then we print that sub array. If sum becomes smaller than inputNumber, then we continue the execution of loop.
Time complexity of this method is O(n)

Java Program To Find Continuous Sub Array In Array Whose Sum Is Equal To Number :

import java.util.Arrays;

public class SubArrayWhoseSumIsNumber {
 static void findSubArray(int[] inputArray, int inputNumber) {
  // Initializing sum with the first element of the inputArray

  int sum = inputArray[0];

  // Initializing starting point with 0

  int start = 0;

  // Iterating through inputArray starting from second element

  for (int i = 1; i < inputArray.length; i++) {
   // Adding inputArray[i] to the current 'sum'

   sum = sum + inputArray[i];

   // If sum is greater than inputNumber then following loop is
   // executed until

   // sum becomes either smaller than or equal to inputNumber

   while (sum > inputNumber && start <= i - 1) {
    // Removing starting elements from the 'sum'

    sum = sum - inputArray[start];

    // Incrementing start by 1

    start++;
   }

   // If 'sum' is equal to 'inputNumber' then printing the sub array

   if (sum == inputNumber) {
    System.out.println("Continuous sub array of " + Arrays.toString(inputArray) + " whose sum is "
      + inputNumber + " is ");

    for (int j = start; j <= i; j++) {
     System.out.print(inputArray[j] + " ");
    }

    System.out.println();
   }
  }
 }

 public static void main(String[] args) {
  findSubArray(new int[] { 42, 15, 12, 8, 6, 32 }, 26);

  findSubArray(new int[] { 12, 5, 31, 13, 21, 8 }, 49);

  findSubArray(new int[] { 15, 51, 7, 81, 5, 11, 25 }, 41);
 }
}

Output :
Continuous sub array of [42, 15, 12, 8, 6, 32] whose sum is 26 is
12 8 6
Continuous sub array of [12, 5, 31, 13, 21, 8] whose sum is 49 is
5 31 13
Continuous sub array of [15, 51, 7, 81, 5, 11, 25] whose sum is 41 is
5 11 25

Another Method To Find Continuous Sub Array Whose Sum Is Equal To Number :

This method is less efficient than the above method. Time complexity of this method is O(n^2). In this method, We try out all the possible continuous sub arrays of the given array. If any sub array is found with sum equal to given number, we print that sub array.

import java.util.Arrays;

public class SubArrayWhoseSumIsNumber {
 static void findSubArray(int[] inputArray, int inputNumber) {
  // Initializing 'sum' to 0

  int sum = 0;

  // Iterating through 'inputArray'

  for (int i = 0; i < inputArray.length; i++) {
   // Assigning inputArray[i] to 'sum'

   sum = inputArray[i];

   for (int j = i + 1; j < inputArray.length; j++) {
    // Adding inputArray[j] to 'sum'

    sum = sum + inputArray[j];

    // If 'sum' is equal to 'inputNumber' then printing the sub
    // array

    if (sum == inputNumber) {
     System.out.println("Continuous sub array of " + Arrays.toString(inputArray) + " whose sum is "
       + inputNumber + " is ");

     for (int k = i; k <= j; k++) {
      System.out.print(inputArray[k] + " ");
     }

     System.out.println();
    }

    // if 'sum' is smaller than 'inputNumber', continue the loop

    else if (sum < inputNumber) {
     continue;
    }

    // if 'sum' is greater than 'inputNumber', then break the loop

    else if (sum > inputNumber) {
     break;
    }
   }
  }
 }

 public static void main(String[] args) {
  findSubArray(new int[] { 42, 15, 12, 8, 6, 32 }, 26);

  findSubArray(new int[] { 12, 5, 31, 13, 21, 8 }, 49);

  findSubArray(new int[] { 15, 51, 7, 81, 5, 11, 25 }, 41);
 }
}

Output :

Continuous sub array of [42, 15, 12, 8, 6, 32] whose sum is 26 is
12 8 6
Continuous sub array of [12, 5, 31, 13, 21, 8] whose sum is 49 is
5 31 13
Continuous sub array of [15, 51, 7, 81, 5, 11, 25] whose sum is 41 is
5 11 25

Share this

Share on FacebookPlus on Google+