Table of Contents
Problem :
Given an array of positive integer and given value X, find Contiguous sub array whose sum is equal to X.
For example:
|
1 2 3 4 5 6 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
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]; } |
Java program to find the Contiguous Subarray with Sum to a Given Value in an array :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
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]; } } } |
|
1 2 3 4 5 6 7 8 |
Sum found between indexes 6 and 7 10 23 ====================== Sum found between indexes 6 and 7 Printing Array values : 10 23 |
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
