[Hackerrank] Sherlock and Array

Problem

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 Nspace-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≤T≤10
1≤N≤105
1≤Ai ≤2×104
1≤i≤N

Sample Input

2
3
1 2 3
4
1 2 3 3

Sample Output

NO
YES

Explanation
For the first test case, no such index exists.
For the second test case, A[1]+A[2]=A[4], therefore index 3 satisfies the given conditions.

Analysis

• First calculate the sum of all elements
• Maintain curr as the cumulated sum in the left parts, when traversing the array
• if (curr == sum - curr - arr[i]), then it means the sum in the left part and right part of arr[i] equals
• Time: 
• O(n), as the array has been traversed twice
• Space
• O(1)

Code

	import java.io.*;
	import java.util.*;
	import java.text.*;
	import java.math.*;
	import java.util.regex.*;
	public class Solution {
	public static void main(String[] args) {
	/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
	Scanner in = new Scanner(System.in);
	int k = in.nextInt();
	for(int i=0; i<k; i++){
	int n = in.nextInt();
	int[] arr = new int[n];
	for(int j=0; j<n; j++){
	arr[j] = in.nextInt();
	}
	System.out.println(decision(arr));
	}
	}
	public static String decision(int[] arr){
	int sum = 0;
	for(int i=0; i<arr.length; i++){
	sum += arr[i];
	}
	//curr is cimulated sum in the left
	int curr = 0;
	for(int j=0; j<arr.length; j++){
	//left part equals right part
	if(curr == sum - arr[j]-curr){
	return "YES";
	}
	curr += arr[j];
	}
	return "NO";
	}
	}

view raw sherlock-and-array.java hosted with ❤ by GitHub