Count pairs of indices with a specific property in an Array
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:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to count pairs satisfying // the condition int count_pairs(vector< int >& a, int k) { // Sorting sort(a.begin(), a.end()); int n = a.size(), ans = 0; for ( int i = 1; i < n; i++) { // Find the index of element equal // to or greater than k * a[i] auto it = lower_bound(a.begin() + i + 1, a.end(), k * a[i]); int j = it - a.begin(); ans += j - i; } return ans; } // Driver code int main() { vector< int > a1 = { 1, 2, 3, 4, 5 }; int k1 = 2; // Function call cout << count_pairs(a1, k1) << endl; return 0; } |
Java
import java.util.*; public class Main { // Function to count pairs satisfying the condition public static int count_pairs(ArrayList<Integer> a, int k) { // Sorting Collections.sort(a); int n = a.size(), ans = 0 ; for ( int i = 1 ; i < n; i++) { // Find the index of element equal to or greater // than k * a[i] int j = Collections.binarySearch( a.subList(i + 1 , n), k * a.get(i)); if (j < 0 ) j = -(j + 1 ) + i + 1 ; else j += i + 1 ; ans += j - i; } return ans; } // Driver code public static void main(String[] args) { ArrayList<Integer> a1 = new ArrayList<>(Arrays.asList( 1 , 2 , 3 , 4 , 5 )); int k1 = 2 ; // Function call System.out.println(count_pairs(a1, k1)); } } |
Python3
from typing import List from bisect import bisect_left def count_pairs(a: List [ int ], k: int ) - > int : # Sorting a.sort() n = len (a) ans = 0 for i in range ( 1 , n): # Find the index of element equal to or greater than k * a[i] j = bisect_left(a, k * a[i], i + 1 , n) ans + = j - i return ans # Driver code if __name__ = = '__main__' : a1 = [ 1 , 2 , 3 , 4 , 5 ] k1 = 2 # Function call print (count_pairs(a1, k1)) |
C#
// C# code for the above approach using System; using System.Collections.Generic; using System.Linq; class GFG { // Function to count pairs satisfying the condition static int CountPairs(List< int > a, int k) { // Sorting a.Sort(); int n = a.Count, ans = 0; for ( int i = 1; i < n; i++) { // Find the index of element equal // to or greater than k * a[i] int j = a.BinarySearch(i + 1, n - i - 1, k * a[i], null ); // If element is not found, the method returns the bitwise // complement of the next larger element in the array if (j < 0) j = ~j; ans += j - i; } return ans; } // Driver's code static void Main( string [] args) { List< int > a1 = new List< int >() { 1, 2, 3, 4, 5 }; int k1 = 2; // Function call Console.WriteLine(CountPairs(a1, k1)); } } |
Javascript
// JavaScript code for the above approach // Function to count pairs satisfying // the condition function count_pairs(a, k) { // Sorting a.sort( function (a, b){ return a-b}); let n = a.length, ans = 0; for (let i = 1; i < n; i++) { // Find the index of element equal // to or greater than k * a[i] let j = i + 1; while (j < n && a[j] < k*a[i]) { j++; } ans += j - i; } return ans; } // Driver code let a1 = [ 1, 2, 3, 4, 5 ]; let k1 = 2; // Function call console.log(count_pairs(a1, k1)); |
8
Time Complexity: O(n * log(n))
Auxilairy Space: O(1)
Contact Us