Count the triplets such that A [ i ] < B [ j ] < C [ k ] | Function to return the count of elements in arr [ ] which are less than the given key ; Modified binary search ; Function to return the count of elements in arr [ ] which are greater than the given key ; Modified binary search ; Function to return the count of the required triplets ; Sort all three arrays ; Iterate for all the elements of array B ; Count of elements in A [ ] which are less than the chosen element from B [ ] ; Count of elements in C [ ] which are greater than the chosen element from B [ ] ; Update the count ; Driver code
< ? php function countLessThan ( & $ arr , $ n , $ key ) { $ l = 0 ; $ r = $ n - 1 ; $ index = -1 ; while ( $ l <= $ r ) { $ m = intval ( ( $ l + $ r ) / 2 ) ; if ( $ arr [ $ m ] < $ key ) { $ l = $ m + 1 ; $ index = $ m ; } else { $ r = $ m - 1 ; } } return ( $ index + 1 ) ; } function countGreaterThan ( & $ arr , $ n , $ key ) { $ l = 0 ; $ r = $ n - 1 ; $ index = -1 ; while ( $ l <= $ r ) { $ m = intval ( ( $ l + $ r ) / 2 ) ; if ( $ arr [ $ m ] <= $ key ) { $ l = $ m + 1 ; } else { $ r = $ m - 1 ; $ index = $ m ; } } if ( $ index == -1 ) return 0 ; return ( $ n - $ index ) ; } function countTriplets ( $ n , & $ a , & $ b , & $ c ) { sort ( $ a ) ; sort ( $ b ) ; sort ( $ c ) ; $ count = 0 ; for ( $ i = 0 ; $ i < $ n ; ++ $ i ) { $ current = $ b [ $ i ] ; $ a_index = -1 ; $ c_index = -1 ; $ low = countLessThan ( $ a , $ n , $ current ) ; $ high = countGreaterThan ( $ c , $ n , $ current ) ; $ count += ( $ low * $ high ) ; } return $ count ; } $ a = array ( 1 , 5 ) ; $ b = array ( 2 , 4 ) ; $ c = array ( 3 , 6 ) ; $ size = sizeof ( $ a ) ; echo countTriplets ( $ size , $ a , $ b , $ c ) ; ? >