 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[].

1. 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
2. Sort this array
3. 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.
4. (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 and A, and second element is sum of A and A, 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), 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:

1. Store sums of all pairs in a hash table
2. Traverse through all pairs again and search for X – (current pair sum) in the hash table.
3. 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)
darkmode