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

  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[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: 

  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