Count pairs from an array whose quotient of division of larger number by the smaller number does not exceed K | Java program for the above approach ; Function to count the number having quotient of division of larger element by the smaller element in the pair not exceeding K ; Sort the array in ascending order ; Store the required result ; Traverse the array ; Store the upper bound for the current array element ; Update the number of pairs ; Print the result ; Driver Code ; Given array , arr [ ] ; Store the size of the array
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { public static int upper_bound ( int arr [ ] , int key ) { int l = - 1 , r = arr . length ; while ( l + 1 < r ) { int m = ( l + r ) >>> 1 ; if ( arr [ m ] <= key ) l = m ; else r = m ; } return l + 1 ; } static void countPairs ( int arr [ ] , int n , int k ) { Arrays . sort ( arr ) ; int ans = 0 ; for ( int i = 0 ; i < n - 1 ; i ++ ) { int high = upper_bound ( arr , k * arr [ i ] ) ; ans += high - i - 1 ; } System . out . println ( ans ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 3 , 9 , 5 } ; int n = arr . length ; int k = 2 ; countPairs ( arr , n , k ) ; } }