## Sunday, 13 September 2015

### Array Aptitude

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

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