current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite

Challenge can be found here

Problem Statement

Watson gives Sherlock an array A of length N. Then he asks him to determine if there exists an element in the array such that the sum of the elements on its left is equal to the sum of the elements on its right. If there are no elements to the left/right, then the sum is considered to be zero. Formally, find an i, such that, A1+A2...Ai-1 =Ai+1+Ai+2...AN.

Input Format: The first line contains T, the number of test cases. For each test case, the first line contains N, the number of elements in the array A. The second line for each test case contains N space-separated integers, denoting the array A.

Output Format: For each test case print YES if there exists an element in the array, such that the sum of the elements on its left is equal to the sum of the elements on its right; otherwise print NO.

Constraints:

\$1 \le T \le 10\$
\$1 \le N \le 10^5\$
\$1 \le Ai \le 2×10^4\$
\$1 \le i \le N\$

I'm having timeout issues on 2 of the test cases

I have tried two different approaches. Both is of \$O(n^2)\$

First was a recursive approach:

public static boolean isEven(int[] arr, int index, int leftSum, int rightSum) {
        int i = index-1;
        int j = index+1;

        while(i > -1) {
            leftSum += arr[i--];
        }

        while(j < arr.length) {
            rightSum += arr[j++];
        }
        return (leftSum == rightSum) ? true : (index == arr.length-1) ? false : isEven(arr, index+1, 0, 0);
    }

Other one was with the use of Navigable map:

public static boolean isEven(NavigableMap<Integer, Integer> map) {
       int left = 0;
       int right = 0;
       int n = map.size();
       while(n-- > 0) {
           left = right = 0;
           for(Integer i : map.tailMap(n+1).values())  right += i; 
           for(Integer j : map.headMap(n).values()) left += j;
           if (left == right) return true;
       }
       return false;
   }

Here is how I read the input:

public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        final int N = s.nextInt();

        for(int i = 0; i < N; i++) {
            int NN = s.nextInt();
            int[] arr = new int[NN];
            for(int j = 0; j < NN; j++) {
                arr[j] = s.nextInt();   
            }
            System.out.println(isEven(arr, 0, 0, 0) ? "YES" : "NO");
        }
    }

To avoid an \$O(n^2)\$ solution, I can't check every element in the array, or can I?

share|improve this question
2  
@Vogel612 "Code Review is about improving existing, working code". My code does work. I just need to improve it's speed. –  Nilzone- Jun 14 at 21:11
    
fuu... sorry I missed the "timeout" in the issues statement, my bad. Are all other test-cases going through cleanly? –  Vogel612 Jun 14 at 21:16
    
@Vogel612. Yes. I can provide a screenshot if you'd like. –  Nilzone- Jun 14 at 21:17
1  
no need, I trust you, and skimming over the code looks like it should work ;) –  Vogel612 Jun 14 at 21:18

1 Answer 1

up vote 5 down vote accepted

Your first example looks much nicer, so I'll focus on that.

First, let's remove the tail recursion in the most obvious way possible:

public static boolean isEven(int[] arr, int index, int leftSum, int rightSum) {
    while (true) {
        int i = index-1;
        int j = index+1;

        while(i > -1) {
            leftSum += arr[i--];
        }

        while(j < arr.length) {
            rightSum += arr[j++];
        }

        if (leftSum == rightSum) {
            return true;
        }
        if (index == arr.length-1) {
            return false
        }

        index += 1;
        leftSum = 0;
        rightSum = 0;
    }
}

Now let's clean it up:

public static boolean isEven(int[] arr) {
    for (int index = 0; index < arr.length; index++) {
        int leftSum = 0;
        for (int i = index -  1; i > -1; i--) {
            leftSum += arr[i];
        }

        int rightSum = 0;
        for (int i = index+1; i < arr.length; i++) {
            rightSum += arr[i];
        }

        if (leftSum == rightSum) {
            return true;
        }
    }

    return false;
}

We can combine the sum variables:

public static boolean isEven(int[] arr) {
    for (int index = 0; index < arr.length; index++) {
        int difference = 0;

        for (int i = index -  1; i > -1; i--) {
            difference += arr[i];
        }
        for (int i = index+1; i < arr.length; i++) {
            difference -= arr[i];
        }

        if (difference == 0) {
            return true;
        }
    }

    return false;
}

Now consider that we don't need to recalculate difference each time. If one iteration we have

|-A-| * |--B--|
1 2 3 4 5 6 7 8

The next we have

|-A-|++ --|-B--|
1 2 3 4 5 6 7 8

Namely, we add 4 to A and subtract 5 from B, which means we add 4 and 5 to the difference. We should also check for empty arrays.

public static boolean isEven(int[] arr) {
    if (arr.length == 0) {
        // Alternatively, return false since there
        // is no element that satisfies the condition.
        throw new IllegalArgumentException();
    }

    int difference = arr[0] - Arrays.stream(arr).sum();
    if (difference == 0) {
        return true;
    }

    for (int i = 1; i < arr.length; i++) {
        difference += arr[i-1];
        difference += arr[i];

        if (difference == 0) {
            return true;
        }
    }

    return false;
}
share|improve this answer
    
Nice suggestion, but it still times out on the same two test cases I'm having troubles with. –  Nilzone- Jun 14 at 21:44
    
@Nilzone- Are you sure it's this function that's the problem? This function should be very fast - certainly faster than parsing the input. –  Veedrac Jun 14 at 21:45
    
I updated the answer so you can see how I read the input. –  Nilzone- Jun 14 at 21:47
    
@Nilzone- It works for me. Are you sure you're not being tripped up by method overloading or something? –  Veedrac Jun 14 at 22:02
    
anything I'm missing here? pastebin.com/PKLHcrr2 –  Nilzone- Jun 14 at 22:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.