Count quadruples from four sorted arrays whose sum is equal to a given value x | Java 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 '
import java . util . * ; class GFG { static int countQuadruples ( int arr1 [ ] , int arr2 [ ] , int arr3 [ ] , int arr4 [ ] , int n , int x ) { int count = 0 ; Map < Integer , Integer > m = new HashMap < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) for ( int j = 0 ; j < n ; j ++ ) if ( m . containsKey ( arr1 [ i ] + arr2 [ j ] ) ) m . put ( ( arr1 [ i ] + arr2 [ j ] ) , m . get ( ( arr1 [ i ] + arr2 [ j ] ) ) + 1 ) ; else m . put ( ( arr1 [ i ] + arr2 [ j ] ) , 1 ) ; for ( int k = 0 ; k < n ; k ++ ) for ( int l = 0 ; l < n ; l ++ ) { int p_sum = arr3 [ k ] + arr4 [ l ] ; if ( m . containsKey ( x - p_sum ) ) count += m . get ( x - p_sum ) ; } return count ; } public static void main ( String [ ] args ) { 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 = arr1 . length ; int x = 30 ; System . out . println ( " Count ▁ = ▁ " + countQuadruples ( arr1 , arr2 , arr3 , arr4 , n , x ) ) ; } }