Post date: Jul 02, 2013 1:18:17 AM
Problem
Find triplets in an array that sum to zero
Solution
1. Find 0, 0, 0
2. Find -a, 0, a
3. Find -a, -b, a + b
4. Find -a - b, a, b
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find triplets in an array that sum to zero
Created Date : 2-July-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
int FindPair(vector<int>& vec, int sum){
int up = vec.size() - 1;
int low = 0;
int pairCount(0);
if(vec[0] < 0 && (sum < 2 * vec[0] || sum >= vec[up])) return 0;
if(vec[0] > 0 && (sum > 2 * vec[up] || sum <= vec[0])) return 0;
int i(0);
while(i < vec.size())
{
if(find(vec.begin(), vec.end(), sum - vec[i]) != vec.end()
&& vec[i] < sum - vec[i]){
cout << "Find triplet {" << setw(3) << left << vec[i];
cout << "," << setw(3) << left << sum - vec[i];
cout << "," << setw(3) << left << - sum;
cout << "} " << endl;
pairCount ++;
}
i++;
while(i < vec.size() && vec[i] == vec[i - 1]) i ++;
}
if(count_if(vec.begin(), vec.end(),
[=](int i) -> bool{ return (i == sum / 2) && (sum % 2 == 0);}) > 1){
cout << "Find triplet {" << setw(3) << left << sum / 2 ;
cout << "," << setw(3) << left << sum / 2;
cout << "," << setw(3) << left << - sum;
cout << "} " << endl;
pairCount ++;
}
return pairCount;
}
static void FindTriplet(vector<int>& vec)
{
if(vec.size() == 0) {
cout << "There is no triplet that sums to zero" << endl;
return;
}
sort(vec.begin(), vec.end());
if(vec[0] > 0 || vec[vec.size() - 1] < 0){
cout << "There is no triplet that sums to zero" << endl;
return;
}
int countNegs = count_if(vec.begin(), vec.end(), [](int i)->bool{ return i < 0;});
int countPoss = count_if(vec.begin(), vec.end(), [](int i)->bool{ return i > 0;});
int countZeros = count_if(vec.begin(), vec.end(), [](int i)->bool{ return i == 0;});
vector<int> negtives(countNegs);
vector<int> positives(countPoss);
vector<int> zeros(countZeros);
int tripletCount(0);
copy_if(vec.begin(), vec.end(), negtives.begin(), [](int i)->bool{ return i < 0;});
copy_if(vec.begin(), vec.end(), positives.begin(), [](int i)->bool{ return i > 0;});
copy_if(vec.begin(), vec.end(), zeros.begin(), [](int i)->bool{ return i == 0;});
if(zeros.size() > 2){ // Find {0, 0, 0}
cout << "Find triplet {0 ,0 ,0 } " << endl;
tripletCount ++;
}
if(zeros.size() > 0){ // Find{ -a, 0, a}
int i = negtives.size() - 1;
int j = 0;
while(i > -1 && j < positives.size()){
if(-negtives[i] < positives[j]){
i --;
}
else if (-negtives[i] > positives[j]){
j ++;
}
else{
cout << "Find triplet {" << setw(3) << left << negtives[i];
cout << ",0 ," << setw(3) << left << positives[j];
cout << "} " << endl;
tripletCount ++;
i --;
while(i > -1 && negtives[i] == negtives[i + 1]) i --;
j ++;
while(j < positives.size() && positives[j] == positives[j - 1]) j ++;
}
}
}
// Find two negtives and one positive
if(negtives.size() > 1 && positives.size() > 0){
for(int i = 0; i < positives.size(); ++ i){
tripletCount += FindPair(negtives, -positives[i]);
}
}
// Find one negtive and two positives
if(positives.size() > 1 && negtives.size() > 0){
for(int i = 0; i < negtives.size(); ++ i){
tripletCount += FindPair(positives, -negtives[i]);
}
}
if(tripletCount == 0){
cout << "There is no triplet that sums to zero" << endl;
}
}
void DoTest(int* arr, int len)
{
cout << "The array is " << endl;
for(int i = 0; i < len; ++i){
cout << setw(3) << left << arr[i];
}
cout << endl;
cout << "The array after sorting " << endl;
for(int i = 0; i < len; ++i){
cout << setw(3) << left << arr[i];
}
cout << endl;
vector<int> vec(arr, arr + len);
FindTriplet(vec);
cout << endl;
}
void main()
{
int arr1[] = {0, 1, 2, 3, 4, 5};
int len = sizeof(arr1) / sizeof(int);
DoTest(arr1, len);
int arr2[] = {0, 0, 2, 3, 4, 5};
len = sizeof(arr2) / sizeof(int);
DoTest(arr2, len);
int arr3[] = {0, 0, 0, 3, 4, 5};
len = sizeof(arr3) / sizeof(int);
DoTest(arr3, len);
int arr4[] = {-2, 0, 0, 0, 3, 4, 5};
len = sizeof(arr4) / sizeof(int);
DoTest(arr4, len);
int arr5[] = {-2, 5};
len = sizeof(arr5) / sizeof(int);
DoTest(arr5, len);
int arr6[] = {-2, -3, -5};
len = sizeof(arr6) / sizeof(int);
DoTest(arr6, len);
int arr7[] = {-1, -2, -3, -5, 0, 2, 3, 5, 1, 2, 4};
len = sizeof(arr7) / sizeof(int);
DoTest(arr7, len);
}
Output
The array is
0 1 2 3 4 5
The array after sorting
0 1 2 3 4 5
There is no triplet that sums to zero
The array is
0 0 2 3 4 5
The array after sorting
0 0 2 3 4 5
There is no triplet that sums to zero
The array is
0 0 0 3 4 5
The array after sorting
0 0 0 3 4 5
Find triplet {0 ,0 ,0 }
The array is
-2 0 0 0 3 4 5
The array after sorting
-2 0 0 0 3 4 5
Find triplet {0 ,0 ,0 }
The array is
-2 5
The array after sorting
-2 5
There is no triplet that sums to zero
The array is
-2 -3 -5
The array after sorting
-2 -3 -5
There is no triplet that sums to zero
The array is
-1 -2 -3 -5 0 2 3 5 1 2 4
The array after sorting
-1 -2 -3 -5 0 2 3 5 1 2 4
Find triplet {-1 ,0 ,1 }
Find triplet {-2 ,0 ,2 }
Find triplet {-3 ,0 ,3 }
Find triplet {-5 ,0 ,5 }
Find triplet {-2 ,-1 ,3 }
Find triplet {-3 ,-1 ,4 }
Find triplet {-3 ,-2 ,5 }
Find triplet {1 ,4 ,-5 }
Find triplet {2 ,3 ,-5 }
Find triplet {1 ,2 ,-3 }
Press any key to continue . . .