## Wednesday, May 4, 2022

### Question 38 : Find the Contiguous Subarray with Sum to a Given Value in an array

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 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;
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 :

``````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;
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 the above program, you will get the below output:

``````Sum found between indexes 6 and 7
10 23
======================
Sum found between indexes 6 and 7
Printing Array values :
10 23
``````

## You may also like

a
Kubernetes AWS Java Coding Question
Microservices Core Java Python
Spring Framework AI/MLSpring Boot