











Sub-array with given sum


Sub-array with given sum in Java.
Given an Array of non negative Integers and a number. You need to print all the starting and ending indices of Subarrays having their sum equal to the given integer.
For Example :-
Input:
arr[ ] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Output:
Sum found between indexes 1 and 4 Sum of elements between indices 1 and 4 is
4 + 0 + 0 + 3 = 7
ALGORITHM:
- Traverse the array from start to end.
- From every index start another loop from i to the end of array to get all subarray starting from i, keep a variable sum to calculate the sum.
- For every index in inner loop update sum = sum + array[j]
- If the sum is equal to the given sum then print the subarray.
JAVA CODE :
class prepinsta {
int ArraySubSum(int arr[], int n, int sum)
{
int currsum, i, j;
// starting point
for (i = 0; i < n; i++) {
currsum = arr[i];
for (j = i + 1; j <= n; j++) {
if (currsum == sum) {
int p = j – 1;
System.out.println(
“Sum found between indexes “ + i
+ ” and “ + p);
return 1;
}
if (currsum > sum || j == n)
break;
currsum = currsum + arr[j];
}
}
System.out.println(“No subarray found”);
return 0;
}
public static void main(String[] args)
{
prepinsta arraysum = new prepinsta();
int arr[] = {1, 4, 0, 0, 3, 10, 5};
int n = arr.length;
int sum = 7;
arraysum.ArraySubSum(arr, n, sum);
}
}
OUTPUT:
Sum found between indexes 1 and 4
Login/Signup to comment