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() == 0) return false;
if (v.size() == 1) return v[0] == 0;
vector<int> v1;
v1.push_back(v[0]);
v1.push_back(-v[0]);
for (int i = 1; i < v.size(); ++ i){
vector<int> v2;
v2.swap(v1);
for (auto j : v2){
v1.push_back(j + v[i]);
v1.push_back(j - v[i]);
}
}
for (auto i : v1){
if (i == 0) return true;
}
return false;
}
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 . . .