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 ; find the ' value ' in the given array ' arr [ ] ' binary search technique is applied ; ' value ' found ; ' value ' not found ; function to count all quadruples from four sorted arrays whose sum is equal to a given value x ; generate all triplets from the 1 st three arrays ; calculate the sum of elements in the triplet so generated ; check if ' x - T ' is present in 4 th array or not ; increment 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 ; bool isPresent ( int arr [ ] , int low , int high , int value ) { while ( low <= high ) { int mid = ( low + high ) / 2 ; if ( arr [ mid ] == value ) return true ; else if ( arr [ mid ] > value ) high = mid - 1 ; else low = mid + 1 ; } return false ; } int countQuadruples ( int arr1 [ ] , int arr2 [ ] , int arr3 [ ] , int arr4 [ ] , int n , int x ) { int count = 0 ; for ( int i = 0 ; i < n ; i ++ ) for ( int j = 0 ; j < n ; j ++ ) for ( int k = 0 ; k < n ; k ++ ) { int T = arr1 [ i ] + arr2 [ j ] + arr3 [ k ] ; if ( isPresent ( arr4 , 0 , n , x - T ) ) count ++ ; } 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 ; }