Print if two subarrays of an array have equal sum

Share

Problem: For a given array of positive or negative integers, check and find if two sub-arrays of equal sums can be obtained by removing exactly one integer from the array.

Problem Explanation: You are given an array a = {5, 2, 6, 4, 3},  if we remove 6, we can obtain two sub-arrays [5, 2 ] and [4, 3]. Similarly, for array a = {-4, 8, -3, -1} if we remove 8, we can obtain two sub-arrays [-4 ] and [-3, -1].

Java Implementation

public void isArrayToSubArrayDivisionPossible(int[] arr) {
    int leftSum=0, totalSum=0;
    for(int i=0;i<arr.length;i++){
        totalSum += arr[i];
    }
    for(int i=0;i<arr.length;i++){
        int rightSum = totalSum - leftSum - arr[i];
        if(leftSum - rightSum==0){
            System.out.println("true");
            printSubArrays(arr,0,i-1);
            printSubArrays(arr,i+1,arr.length-1);
            return;
        }
        leftSum = leftSum + arr[i];
    }
    System.out.println("false");
}

public void printSubArrays(int[] arr, int startIndex, int endIndex) {
    System.out.print("[");
    for(int i=startIndex<=endIndex;i++){
        System.out.print(arr[i]);
    }
    System.out.print("]");
}
TimeComplexity: O(n)

Note: If you find any other better way to approach to this problem or you find any issue/error in above code snippets/approaches – please share it in the comments section below and get a chance to enrol free of cost for an online Live Data Structure and Algorithm course (specially designed for interview preparation for software companies like Amazon, Google, Facebook, FlipKart, SnapDeal, HealthKart…)