Count pairs of indices with a specific property in an Array – GeeksforGeeks

Given an array a[] of size n containing only non-negative integers, and an integer k, the task is to find the number of pairs of indices (i, j) such that i < j and k * a[i] ≤ a[j].

Examples:

Input: a[] = {3, 5, 2, 4}, n = 4, k = 2
Output: 6
Explanation: The pairs satisfying the condition are: (1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 5)

Input: a[] = {2, 4, 1, 6, 3}, n = 5, k = 3
Output: 5
Explanation: The pairs satisfying the condition are: (1, 3), (1, 5), (2, 5), (3, 4), (3, 5)

Approach: This can be solved with the following idea:

Sort the array, and find the index of the element equal to or greater than k * a[i], then all the elements will satisfy the condition.

Steps involved in the implementation of code

• Sort the array in non-decreasing order.
• For each index, i starting from the second, use binary search to find the index j such that k * a[i] ≤ a[j] and j > i.
• Add the number of indices found by binary search to the answer.
• Return the final answer.

Below is the implementation of the above approach:

Time Complexity: O(n * log(n))
Auxilairy Space: O(1)