Count quadruples from four sorted arrays whose sum is equal to a given value x | C ++ implementation to count quadruples from four sorted arrays whose sum is equal to a given value x ; function to count all quadruples from four sorted arrays whose sum is equal to a given value x ; unordered_map ' um ' implemented as hash table for < sum , frequency > tuples ; count frequency of each sum obtained from the pairs of arr1 [ ] and arr2 [ ] and store them in ' um ' ; generate pair from arr3 [ ] and arr4 [ ] ; calculate the sum of elements in the pair so generated ; if ' x - p _ sum ' is present in ' um ' then add frequency of ' x - p _ sum ' to ' count ' ; required count of quadruples ; Driver program to test above ; four sorted arrays each of size ' n '
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countQuadruples ( int arr1 [ ] , int arr2 [ ] , int arr3 [ ] , int arr4 [ ] , int n , int x ) { int count = 0 ; unordered_map < int , int > um ; for ( int i = 0 ; i < n ; i ++ ) for ( int j = 0 ; j < n ; j ++ ) um [ arr1 [ i ] + arr2 [ j ] ] ++ ; for ( int k = 0 ; k < n ; k ++ ) for ( int l = 0 ; l < n ; l ++ ) { int p_sum = arr3 [ k ] + arr4 [ l ] ; if ( um . find ( x - p_sum ) != um . end ( ) ) count += um [ x - p_sum ] ; } return count ; } int main ( ) { int arr1 [ ] = { 1 , 4 , 5 , 6 } ; int arr2 [ ] = { 2 , 3 , 7 , 8 } ; int arr3 [ ] = { 1 , 4 , 6 , 10 } ; int arr4 [ ] = { 2 , 4 , 7 , 8 } ; int n = sizeof ( arr1 ) / sizeof ( arr1 [ 0 ] ) ; int x = 30 ; cout << " Count ▁ = ▁ " << countQuadruples ( arr1 , arr2 , arr3 , arr4 , n , x ) ; return 0 ; }