We need to find whether there exists 4 numbers a, b, c and d (all numbers should be at different indices) in an array whose sum equals to a constant k.
Now its hashing based solution goes like this: Make a hash having key as sum of every pair in array and value as array of pairs of indices whose sum is the key. Now iterate over every pair in array and try to find the remaining sum in the hash table we made, while also checking that no 2 indices should be common.
While the above solution is fine, a solution I saw on geeksforgeeks.com did this: In the hash table the value is a pair instead of array of pairs. It only stores the last pair which concludes to a sum. It clearly looks wrong to me but I still can't find a test case where it fails.
Their code:
// A hashing based CPP program to find if there are
// four elements with given sum.
#include <bits/stdc++.h>
using namespace std;
// The function finds four elements with given sum X
void findFourElements (int arr[], int n, int X)
{
// Store sums of all pairs in a hash table
unordered_map<int, pair<int, int>> mp;
for (int i = 0; i < n-1; i++)
for (int j = i+1; j < n; j++)
mp[arr[i] + arr[j]] = {i, j};
// Traverse through all pairs and search
// for X - (current pair sum).
for (int i = 0; i < n-1; i++)
{
for (int j = i+1; j < n; j++)
{
int sum = arr[i] + arr[j];
// If X - sum is present in hash table,
if (mp.find(X - sum) != mp.end())
{
// Making sure that all elements are
// distinct array elements and an element
// is not considered more than once.
pair<int, int> p = mp[X - sum];
if (p.first != i && p.first != j &&
p.second != i && p.second != j)
{
cout << arr[i] << ", " << arr[j] << ", "
<< arr[p.first] << ", "
<< arr[p.second];
return;
}
}
}
}
}
// Driver program to test above function
int main()
{
int arr[] = {10, 20, 30, 40, 1, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int X = 91;
findFourElements(arr, n, X);
return 0;
}
How can I find a testcase where this code fails, or if it is correct, how?
The algorithm is correct. Consider a quadruple (a, b, c, d) which satisfies the following: (1) arr[a] + arr[b] + arr[c] + arr[d] == k; (2) a < b < c < d.
It is obvious that four distinct element of the array sum to k if and only if such quadruple (a, b, c, d) exists.
Now consider the pair (a, b). You have mentioned the program records the last pair (e, f) (e < f) that is a compliment of (a, b) (i.e. arr[a] + arr[b] + arr[e] + arr[f] == k). Note that since (e, f) is the last pair with such property, so e >= c. Therefore a < b < e < f. Now we have found a valid quadruple (a, b, e, f).
Since the second loop traverse through all pairs, the pair (a, b) must have been visited, and the quadruple must have been detected. Therefore the algorithm is correct.