Hackerrank's Sherlock and Array

Question

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?

@Vogel612 "Code Review is about improving existing, working code". My code does work. I just need to improve it's speed. — Nilzone-, Jun 14 '15 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 '15 at 21:16
no need, I trust you, and skimming over the code looks like it should work ;) — Vogel612, Jun 14 '15 at 21:18

Veedrac · Accepted Answer · 2015-06-14 21:46:38Z

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;
}

Nice suggestion, but it still times out on the same two test cases I'm having troubles with. — Nilzone-, Jun 14 '15 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 '15 at 21:45
@Nilzone- It works for me. Are you sure you're not being tripped up by method overloading or something? — Veedrac, Jun 14 '15 at 22:02

Koushik Jay · Answer 2 · 2016-09-09 17:44:53Z

This what my code looks like. If the array is length 1 I have put it in a if statement else the whole array needs to be traversed. That way save some time.

Another thing important I have done is that while taking all the input I have calculated the sum of them , as I am left traversing then the sum of the array is actually rightSum (rightSum = sum- value of current Index).

While I am traversing the left one increased value by adding previous index and right one decreases by the current Index value.

Here is my code

 // TODO code application logic here
    Scanner lab = new Scanner(System.in);
    int leftSum = 0;
    int rightSum = 0;
    int testCases = lab.nextInt();
    for (int i = 0; i < testCases; i++) {
        int length = lab.nextInt();
        int temp[] = new int[length];

        for (int j = 0; j < length; j++) {
            temp[j] = lab.nextInt();
            rightSum += temp[j];
        }
        if (length == 1) {
            System.out.println("YES");
        } else {

            rightSum = rightSum - temp[0];
            for (int j = 1; j < length; j++) {
                if (j == length - 1) {
                    System.out.println("NO");
                    break;
                }
                rightSum = rightSum - temp[j];
                leftSum = leftSum + temp[j - 1];
                if (leftSum == rightSum) {
                    System.out.println("YES");
                    break;
                }
            }
        }
        rightSum = 0;
        leftSum = 0;

    }

asked	1 year ago
viewed	2288 times
active	2 months ago

current community

your communities

more stack exchange communities

Hackerrank's Sherlock and Array

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged java performance algorithm programming-challenge search or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Hackerrank's Sherlock and Array

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged java performance algorithm programming-challenge search or ask your own question.

Related

Hot Network Questions