Sherlock and Array | HackerRank Solution [Easy]

Problem

Watson gives Sherlock an array of integers. His challenge is to find an element of the array such that the sum of all elements to the left is equal to the sum of all elements to the right.

HackerRank Problem Link

Input

The first line contains T, the number of test cases.
The next T pairs of lines each represent a test case:
– The first line contains n, the number of elements in the array
– The second line contains n space-separated integers a[i]

Output

Determine whether there is an element that meets the criterion. If there is, return YES. Otherwise, return NO.

Constraints

• 1 <= T <= 10
• 1 <= n <= 10⁵
• 1 <= a[i] <= 2 x 10⁴
• 0 <= i < n

Sample Input

2
3
1 2 3
4
1 2 3 3

Sample Output

NO
YES

Solution

Approach: Sliding Window technique

Pseudocode

Maintain two variables, leftSum and rightSum such that at given i:
leftSum = a0 + a1 + a2 + ... ai-1
rightSum = ai+1 + ai+2 + ai+3 + ... an-1

Traverse the array a (0 <= i < n) and if at any point, 
leftSum == rightSum, return true

Also read:

Code Implementation

//
//  main.cpp
//  Sherlock and Array
//
//  Created by Himanshu on 27/03/22.
//

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool solve (vector<int> a, int n) {
    long int leftSum = 0, rightSum = 0;

    for(int i=1; i<n; i++) {
        rightSum += a[i];
    }
    
    for (int i=0,j=1; i<(n-1); i++,j++) {
        
        if (leftSum == rightSum) {
            return true;
        }
        
        leftSum += a[i];
        rightSum -= a[j];
    }
    
    return false;
}

int main() {
    int T, n;
    cin>>T;
    
    while (T--) {
        cin>>n;
        vector<int> a(n);
        
        for(int i=0; i<n; i++) {
            cin>>a[i];
        }
        
        if(n == 1 || solve(a, n)) {
            cout<<"YES"<<endl;;
        } else {
            cout<<"NO"<<endl;
        }
    }

 return 0;
}

Time complexity: O(n), where n is the size of input array