LeftSubArray_equal_RightSubarray.java

package Programs.Arrays;

public class LeftSubArray_equal_RightSubarray {

    /**
     * Question Description:
     * Given, an array of size n. Find an element which divides the array in two sub-arrays with equal sum.
     * geeks for geeks url:
     * https://www.geeksforgeeks.org/find-element-array-sum-left-array-equal-sum-right-array/
     *
     * Examples:
     *
     * Input : 1 4 2 5
     * Output : 2
     * Explanation : If 2 is the partition,
     *       subarrays a  re : {1, 4} and {5}
     *
     * Input : 2 3 4 1 4 5
     * Output : 1
     * Explanation : If 1 is the partition,
     *  Subarrays are : {2, 3, 4} and {4, 5}
     *
     * difficulty level: 3/10
     * Tags: #airtel #array #arrays
     *
     */

    public static void main(String[] args) {

        int arr[] = {1,4,2,5};
        //int arr[] = {2,3,4,1,4,5};
        //int arr[] = {2,3,4,1,9,-5};

        int dividingElement = find_dividing_element2(arr);
        System.out.println("divding element is : " + dividingElement  );
    }

    /**
     *     First self Attempt - working fine
     *     complexity: O(n) square
     */
    private static int find_dividing_element(int arr[]){
        int leftSubArrayTotal = arr[0];

        for(int i=1;i<arr.length;i++){
            int rightSubArrayTotal = 0;
            for(int j=i+1;j<arr.length;j++)
            {
                rightSubArrayTotal +=arr[j];
            }// end of j
            if(leftSubArrayTotal==rightSubArrayTotal)
                return arr[i];
            leftSubArrayTotal += arr[i];
        }// end of i
        return -1;
    }

    /**
     * Second self Attempt - working, best i could do :)
     * Complexity: O(n)
     */
    private static int find_dividing_element2(int arr[]){
        int leftPointer=0;
        int rightPointer=arr.length-1;
        int leftSubArrayTotal = arr[leftPointer];
        int rightSubArrayTotal = arr[rightPointer];
        while(leftPointer<rightPointer){
            if(leftSubArrayTotal>rightSubArrayTotal)
                rightSubArrayTotal += arr[--rightPointer];
            else
                leftSubArrayTotal +=  arr[++leftPointer];
        } // end of while loop
        if(leftSubArrayTotal==rightSubArrayTotal)
            return arr[leftPointer];
        else
            return -1;
    }

}