Find four elements that sum to a given value
given an array ,find the 4 elements whose sum is equal to given value
N = 5, K = 3
A[] = {0,0,2,1,1}
Output: 0 0 1 2 method 1: easy method:
generate all possible quadruples by using 4 loops and compare the sum of every quadruple with X.
implementation:
void frnos(int A[], int n, int X)
{
// Fix the first element and find other three
for (int i = 0; i < n - 3; i++)
{
// Fix the second element and find other two
for (int j = i + 1; j < n - 2; j++)
{
// Fix the third element and find the fourth
for (int k = j + 1; k < n - 1; k++)
{
// find the fourth
for (int l = k + 1; l < n; l++)
{
if (A[i] + A[j] + A[k] + A[l] == X)
cout << A[i] <<", " << A[j]
<< ", " << A[k] << ", " << A[l];
}
}
}
}
} Time Complexity: O(n^4)
space complexity:O(1)
METHOD 2: (use sorting)
1) sort the array
2))the first two loops will be the same as the above method
3)instead of using two again , we will find it like this sdfghjkl
implementation:
void frno(int A[], int n, int X)
{
int l, r;
sort(A,A+n); //sort the array
/* Now fix the first 2 elements
one by one and find
the other two elements */
for (int i = 0; i < n - 3; i++)
{
for (int j = i+1; j < n - 2; j++)
{
// Initialize two variables as
// indexes of the first and last
// elements in the remaining elements
l = j + 1;
r = n-1;
// To find the remaining two
// elements, move the index
// variables (l & r) toward each other.
while (l < r)
{
if( A[i] + A[j] + A[l] + A[r] == X)
{
cout << A[i]<<", " << A[j] <<
", " << A[l] << ", " << A[r];
l++; r--;
}
else if (A[i] + A[j] + A[l] + A[r] < X)
l++;
else // A[i] + A[j] + A[l] + A[r] > X
r--;
}
}
}
} Time Complexity: O(n^3)
space complexity:O(1)
Method 1: Two Pointers Algorithm.
Approach: Let the input array be A[].
- Create an array of size of n*(n-1)/2 where n is the size of A[] and store sum of all possible pairs in it
- Sort this array
- Now the problem reduces to find two elements in aux[] with sum equal to X. We can use method 1 of this post to find the two elements efficiently.
- (An element of aux[] represents a pair from A[]. While picking two elements from aux[], we must check whether the two elements have an element of A[] in common. For example, if first element sum of A[1] and A[2], and second element is sum of A[2] and A[4], then these two elements of aux[] don’t represent four distinct elements of input array A[].
Below is the implementation of the above approach:
struct pairSum {
// index (int A[]) of first element in pair
int first;
// index of second element in pair
int sec;
// sum of the pair
int sum;
};
bool noCommon(pairSum a, pairSum b)
{
if (a.first == b.first || a.first == b.sec
|| a.sec == b.first || a.sec == b.sec)
return false;
return true;
}
void findFourElements(int arr[], int n, int X)
{
int i, j;
// Create an temporary array
// to store all pair sums
int size = (n * (n - 1)) / 2;
pairSum temp[size];
// Generate all possible pairs
// from A[] and store sums
// of all possible pairs in temp[]
int k = 0;
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
temp[k].sum = arr[i] + arr[j];
temp[k].first = i;
temp[k].sec = j;
k++;
}
}
// Sort the temp[] array using
// library function for sorting
qsort(temp, size, sizeof(temp[0]), compare);
// Now start two index variables
// from two corners of array
// and move them toward each other.
i = 0;
j = size - 1;
while (i < size && j >= 0) {
if ((temp[i].sum + temp[j].sum == X &&
&& temp[i].first != temp[j].first && temp[i].first != temp[j].sec
&& temp[i].sec != temp[j].first && temp[j].sec !=temp[j].sec) {
cout << arr[temp[i].first] << ", "
<< arr[temp[i].sec] << ", "
<< arr[temp[j].first] << ", "
<< arr[temp[j].sec] << endl;
return;
}
else if (temp[i].sum + temp[j].sum < X)
i++;
else
j--;
}
} - Time complexity: O(n^2Logn).
The step 1 takes O(n^2) time. The second step is sorting an array of size O(n^2). Sorting can be done in O(n^2Logn) time using merge sort or heap sort or any other O(nLogn) algorithm. The third step takes O(n^2) time. So overall complexity is O(n^2Logn). - Auxiliary Space: O(n^2).
The size of the auxiliary array is O(n^2). The big size of the auxiliary array can be a concern in this method.
Method 2: Hashing Based Solution [O(n2)]
Approach:
- Store sums of all pairs in a hash table
- Traverse through all pairs again and search for X – (current pair sum) in the hash table.
- If a pair is found with the required sum, then make sure that all elements are distinct array elements and an element is not considered more than once.
implementation:
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; } } } } }
- Time complexity: O(n^2).
Nested traversal is needed to store all pairs in the hash Map. - Auxiliary Space: O(n^2).
All n*(n-1) pairs are stored in hash Map so the space required is O(n^2)
No comments