Array Aptitude

Divide array in two part such that sum of array left to partition index i  is equal to sum of array right to partition index i.

That is A[0]+A[1]...+A[i-1]=A[i+1]+....+A[n]

This is slightly tricky question but very easy to solve and code ,if you find the trick.

Algorithm:

• Find the cumulative sum at each index of array
• loop through array and check  A[i-1]==A[n]-A[i] , If condition Satisfy for any index i, means array can be partition in two group with this condition,So print "YES" else "NO"
• Use special case if array has only 1 element then print YES
• if array has only two element then print "NO"

C++ Source Code

1. #include <cmath>
2. #include <cstdio>
3. #include <vector>
4. #include <iostream>
5. #include <algorithm>
6. using namespace std;
9. int main() {
10.     int n,key;
11.     vector<int> arr;
12.     cout<<"No of element in array:";
13.     cin>>n;
14.     cout<<"Enter Array data :";
15.     while(n--){
16.             cin>>key;
17.             arr.push_back(key);
18.     }
19.     //Special case for 1 and 2 element array
20.     if(arr.size()==1){
21.         cout<<"YES"<<endl;
22.     }
23.     else if(arr.size()==2){
24.         cout<<"NO"<<endl;
25.     }
26.     else{
27.         //find cumulative Sum at each index
28.         for(int i=1;i<arr.size();i++){
29.             arr[i]+=arr[i-1];
30.         }
31.          int flag=0;
32.           n=arr.size()-1;
33.         //check is arr[i-1]==arr[n]-arr[i]
34.         for(int i=1;i<n;i++){
35.             if(arr[i-1]==(arr[n]-arr[i])){
36.                 flag=1;
37.                 break;
38.             }
39.         }
40.         if(flag)
41.             cout<<"YES"<<endl;
42.         else
43.             cout<<"NO"<<endl;
44.     }
45.     return 0;
46. }

Output :