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[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;
  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. }

Output :



No comments:

Post a comment

THANKS FOR UR GREAT COMMENT

Blogger Widgets