Check if sum of left side of array equal to right side of array in o(n)

Question

I was given an array of numbers (integer) and I need to return the element if the sum of numbers in his right side equals to the sum of numbers in his left size in o(n).

For example the array {1,2,2,9,3,2} the program should print 9 because 1+2+2 = 5 and 3+2=5

I attached my code but it's not o(n) complexity. appreciate your help.

Thanks.

public class Program {
    public static void checkIfEqualOption1(int[] arr){
        int sumRight = 0;
        int sumLeft=0;
        //sumRight+=numbers[0];
        for (int i=0; i < arr.length; i++){
            if (i>0){
                sumRight+=arr[i-1];
                for (int j=i+1; j<arr.length; j++){
                    sumLeft+=arr[j];
                }
                if (sumRight==sumLeft){
                    System.out.println("\nFound = "+arr[i]);
                    break;
                }
            }
        }

    }

    public static void print(int[] arr){
        for (int i=0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("Hi");
        int[] numbers = {1,2,2,9,3,2};
        System.out.println("Array numbers:");
        for (int i=0; i < numbers.length; i++){
            System.out.print(numbers[i] + " ");
        }
        System.out.println("\n");
        checkIfEqualOption1(numbers);
    }
}

Solution 1

Start with the observation that for each i

arraySum(0, i) + arraySum(i+1, n) == arrayTotal

so

arraySum(i+1, n) == arrayTotal - arraySum(0, i);
^^^^^^^^^^^^^^^^                 ^^^^^^^^^^^^^^^
Sum on the right                 Sum on the left

Compute the arrayTotal in the first pass; then walk the array from the left, computing the partial sum. Stop once you reach a position where

partialSum == arrayTotal - partialSum

Solution 2

This should work in O(n), you don't need to sort the array:

public class Program {

    public static void checkIfEqualOption1(int[] arr){

        int sumTotal=0;
        for (int i=0; i < arr.length; i++){ // O(arr.length)
            sumTotal += arr[i];
        }

        int sumRight = 0;
        int sumLeft=0;
        for (int i=1; i < arr.length-1; i++){ // O(arr.length)
            sumLeft += arr[i-1];
            sumRight = sumTotal - arr[i] - sumLeft;
            if (sumRight == sumLeft){
                System.out.println("\nFound = "+arr[i]);
                break;
            }
        }
   }


   public static void main(String[] args) {

     int[] numbers = {1,2,2,9,3,2};
     System.out.println("Array numbers:");
     for (int i=0; i < numbers.length; i++){
          System.out.print(numbers[i] + " ");
     }
     System.out.println("\n");
     checkIfEqualOption1(numbers);
   }

}

This outputs:

Array numbers:
1 2 2 9 3 2


Found = 9