Count pairs from an array whose quotient of division of larger number by the smaller number does not exceed K | Javascript 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 ; Given array , arr [ ] ; Store the size of the array
function upper_bound ( arr , key ) { let l = - 1 , r = arr . length ; while ( l + 1 < r ) { let m = ( l + r ) >>> 1 ; if ( arr [ m ] <= key ) l = m ; else r = m ; } return l + 1 ; } function countPairs ( arr , n , k ) { arr . sort ( ) ; let ans = 0 ; for ( let i = 0 ; i < n - 1 ; i ++ ) { let high = upper_bound ( arr , k * arr [ i ] ) ; ans += high - i - 1 ; } document . write ( ans ) ; } let arr = [ 2 , 3 , 9 , 5 ] ; let n = arr . length ; let k = 2 ; countPairs ( arr , n , k ) ;