Count of Quadruplets with Given Sum in C++

We are given with four arrays. Goal is to find quadruplets of elements from the four arrays that have sum equal to a given Sum value. The elements selected should be such that all 4 elements belong to different arrays.

We will do this by traversing all arrays using for loop and check if A[i]+B[j]+C[k]+D[l]==sum. If yes increment count.

Let us understand with examples −

Input −

A[]={ 1,3,1}, B[]={ 2,4,5 } , C[]={ 1,1,2 } , D[]= { 4,4,0} Sum=5

Output − Count of quadruplets with given sum are − 2

Explanation −

2 quadrutplets are:
(A[0],B[0],C[2],D[2]) → (1,2,2,0), sum=5
(A[2],B[0],C[2],D[2]) → (1,2,2,0), sum=5

Input −

A[]={ 1,1,1}, B[]={ 1,1,1 } , C[]={ 1,1,1 } , D[]= {1,1,1} Sum=3

Output − Count of quadruplets with given sum are − 0

Explanation −Sum of all quadruplets will be 4 which is > 3.

Approach used in the below program is as follows

• We take integer arrays first[], second[], third[] and fourth[] of equal length initialized with random numbers.

• Take variables first_size, second_size, third_size, fourth_size to store their respective lengths.

• Take variable sum for given sum value.

• Function quadruplets(int first[], int second[], int third[], int fourth[], int first_size, int second_size, int third_size, int fourth_size, int sum) takes all arrays and their length with sum and returns count of quadruplets with given sum.

• Traverse each array using FOR loops

• Outermost loop 0<=i<first_size for first[], then 0<=j<second_size for second[] , 0<=k<third_size for third[] and 0<=l<fourth_size for fourth[].

• Compare if first[i] + second[j] + third[k] + fourth[l] == sum. If true increment count.

• At the end of all loops count will have quadruplets with given sum.

• Return count as result.

Example

 Live Demo

#include <bits/stdc++.h>
using namespace std;
int quadruplets(int first[], int second[], int third[], int fourth[], int first_size, int second_size, int
third_size, int fourth_size, int sum){
   int count = 0;
   for (int i = 0; i < first_size; i++){
      for (int j = 0; j < second_size; j++){
         for (int k = 0; k < third_size; k++){
            for (int l = 0; l < fourth_size; l++){
               if (first[i] + second[j] + third[k] + fourth[l] == sum){
                  count++;
               }
            }
         }
      }
   }
   return count;
}
int main(){
   int first[] = { 7, -8 };
   int second[] = { 7, -2 };
   int third[] = { 4, -2 };
   int fourth[] = { 3, -4 };
   int first_size = sizeof(first) / sizeof(first[0]);
   int second_size = sizeof(second) / sizeof(second[0]);
   int third_size = sizeof(third) / sizeof(third[0]);
   int fourth_size = sizeof(fourth) / sizeof(fourth[0]);
   int sum= 0;
   cout<<"Count of quadruplets with given sum are: "<<quadruplets(first, second, third, fourth, first_size, second_size, third_size, fourth_size, sum);
   return 0;
}

Output

If we run the above code it will generate the following output −

Count of quadruplets with given sum are: 1