Count pairs from an array whose quotient of division of larger number by the smaller number does not exceed K

Count pairs from an array whose quotient of division of larger number by the smaller number does not exceed K

Given an array arr[] of size N, and an integer K, the task is to count the number of pairs from the given array whose quotient of division of the larger element by the smaller element in the pair does not exceed K.

Examples:

Input: arr[] = {3, 12, 5, 13}, K=2
Output: 2
Explanation: Pairs satisfying the given conditions are (3, 5) and (12, 13).

Input: arr[] = {2, 3, 9, 5}, K=2
Output: 3
Explanation: Pairs satisfying the given conditions are (2, 3), (3, 5) and (5, 9).

Naive Approach: The simplest approach is to generate all possible pairs from the given array, and for each pair, check if required conditions are satisfied. For the pairs satisfying the condition, increment count by 1. After checking for all the pairs, print the count obtained. 
Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: To optimize the above approach, the idea is to sort the array in ascending order and then for each array element arr[i], use Binary Search to find the index, say high, of the element which is just greater than K * arr[i]. All the elements in the range [i + 1, high – 1] will form a pair with arr[i]. 
Follow the steps below to solve the problem:

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> 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; }

Time Complexity: O(N*log(N))
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)