HackerRank 'Sherlock and Array' Solution

by Srikant Padala on April 19, 2016, 8:22 am


Explanation


Find the prefix sum corresponding to the array. Prefix sum is basically sum of all elements of elements of the array upto and including a[i].

Left sum is pre[i-1].

Right sum is pre[n-1] - pre[i].


Sherlock and Array Problem Statement

Video

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

typedef long long ll;
ll pre[100000];

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int T;
    cin >> T;
    while(T--) {
        ll n,x;
        cin >> n;
        for(ll i=0; i < n; i++) {
            cin >> x;
            if(i == 0) pre[i] = x;
            else pre[i] = pre[i-1] + x;
        }
        bool flag = false;
        for(ll i=1; i < n-1; i++) {
            if(pre[i-1] == pre[n-1] - pre[i]) {
                flag = true;
                break;
            }
        }
        if(flag == true || n == 1) cout << "YES
";
        else cout << "NO
";
    }
    return 0;
}

Coming Soon.