Question
Given an array of +ve as well as -ve numbers, find out whether it is possible or not to convert it to 0 by adding/subtracting operations on all the elements.
e.g arr[]={1,2,3}
YES (1+2-3)
arr[]={3,6,2}
3+6-2 != 0
3-6-2 !=0
-3-6-2 !=0
-3-6+2 !=0
-3+6-2 !=0
-3+6+2 !=0
3-6+2 !=0
3+6+2 !=0
Hence ans= NO
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Sum of an array with adding/subtracting operations on all the elements.
Created Date : 19-01-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <vector>
#include <iterator>
using namespace std;
bool Sum(vector<int> v)
{
if (v.size() == 1){
return v[0] == 0;
}
int n = v[v.size() - 1];
v.pop_back();
vector<int> v1(v), v2(v);
v1[0] += n;
v2[0] -= n;
return Sum(v1) || Sum(v2);
}
void DoTest(vector<int> v)
{
copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
cout << " -- ";
if (Sum(v)){
cout << "YES" << endl;
}
else{
cout << "NO" << endl;
}
}
int main()
{
vector<int> testCases[]{
{ 2, 3, 6 },
{ 2, 4, 6 },
{ 0 },
{ 2, 3, 6, 1 },
{ 2, 3, 6, 2 }
};
for (auto i : testCases){
DoTest(i);
}
return 0;
}
Output
2 3 6 -- NO
2 4 6 -- YES
0 -- YES
2 3 6 1 -- YES
2 3 6 2 -- NO
Press any key to continue . . .