Sub-array with given sum

January 29, 2021

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