Count pairs from an array whose quotient of division of larger number by the smaller number does not exceed K | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void countPairs ( int arr [ ] , int n , int k ) { sort ( arr , arr + n ) ; int ans = 0 ; for ( int i = 0 ; i < n - 1 ; i ++ ) { int high = upper_bound ( arr , arr + n , k * arr [ i ] ) - arr ; ans += high - i - 1 ; } cout << ans ; } int main ( ) { int arr [ ] = { 2 , 3 , 9 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 2 ; countPairs ( arr , n , k ) ; return 0 ; }