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 the required conditions are satisfied. For the pairs satisfying the condition, increment count by 1. After checking for all the pairs, print the count obtained.
C++
#include <iostream> #include <vector> using namespace std; // function to count the number of pairs int countPairs(vector< int >& arr, int K) { int n = arr.size(); int count = 0; // initialize count to 0 // generate all possible pairs for ( int i = 0; i < n - 1; i++) { for ( int j = i + 1; j < n; j++) { int larger = max(arr[i], arr[j]); int smaller = min(arr[i], arr[j]); // check if the quotient of division of larger and smaller element does not exceed K if (larger / smaller < K) { count++; // increment count if condition is satisfied } } } return count; } int main() { vector< int > arr = {3, 12, 5, 13}; int K = 2; int count = countPairs(arr, K); // call the function to count the number of pairs // output the final count cout << count << endl; return 0; } //This code is contributed by Naveen Gujjar from Haryana |
Java
/*package whatever //do not write package name here */ import java.io.*; // Java code implementation class Beginner{ // function to count the number of pairs public static int countPairs( int [] arr, int K) { int n = arr.length; int count = 0 ; // initialize count to 0 // generate all possible pairs for ( int i = 0 ; i < n - 1 ; i++) { for ( int j = i + 1 ; j < n; j++) { int larger = Math.max(arr[i], arr[j]); int smaller = Math.min(arr[i], arr[j]); // check if the quotient of division of larger and smaller element does not exceed K if (larger / smaller < K) { count++; // increment count if condition is satisfied } } } return count; } public static void main(String[] args){ int [] arr = { 3 , 12 , 5 , 13 }; int K = 2 ; int count = countPairs(arr, K); // call the function to count the number of pairs // output the final count System.out.println(count); } } // The code is contributed by Nidhi goel. |
Python3
# function to count the number of pairs def countPairs(arr, K): n = len (arr) count = 0 # initialize count to 0 # generate all possible pairs for i in range (n - 1 ): for j in range (i + 1 , n): larger = max (arr[i], arr[j]) smaller = min (arr[i], arr[j]) # check if the quotient of division of larger and smaller element does not exceed K if larger / / smaller < K: count + = 1 # increment count if condition is satisfied return count # main function if __name__ = = '__main__' : arr = [ 3 , 12 , 5 , 13 ] K = 2 count = countPairs(arr, K) # call the function to count the number of pairs # output the final count print (count) |
C#
using System; using System.Collections.Generic; class MainClass { // function to count the number of pairs static int CountPairs(List< int > arr, int K) { int n = arr.Count; int count = 0; // initialize count to 0 // generate all possible pairs for ( int i = 0; i < n - 1; i++) { for ( int j = i + 1; j < n; j++) { int larger = Math.Max(arr[i], arr[j]); int smaller = Math.Min(arr[i], arr[j]); // check if the quotient of division of // larger and smaller element does not // exceed K if (larger / smaller < K) { count++; // increment count if condition // is satisfied } } } return count; } static void Main() { List< int > arr = new List< int >{ 3, 12, 5, 13 }; int K = 2; int count = CountPairs( arr, K); // call the function to count the // number of pairs // output the final count Console.WriteLine(count); } } // This code is contributed by sarojmcy2e |
Javascript
// function to count the number of pairs function countPairs(arr, K) { const n = arr.length; let count = 0; // initialize count to 0 // generate all possible pairs for (let i = 0; i < n - 1; i++) { for (let j = i + 1; j < n; j++) { const larger = Math.max(arr[i], arr[j]); const smaller = Math.min(arr[i], arr[j]); // check if the quotient of division of larger and smaller element does not exceed K if (Math.floor(larger / smaller) < K) { count += 1; // increment count if condition is satisfied } } } return count; } // main function ( function main() { const arr = [3, 12, 5, 13]; const K = 2; const count = countPairs(arr, K); // call the function to count the number of pairs // output the final count console.log(count); })(); |
2
Time Complexity: O(N2)
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:
- Initialize a variable, say ans, to store the required number of pairs.
- Sort the given array in ascending order.
- Traverse the array arr[] using a variable, say i
- Store the index of the upper bound of value 2 * arr[i] in a variable, say high.
- Update the value of ans by adding high – i – 1 to it.
- Print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the number // having quotient of division // of larger element by the smaller // element in the pair not exceeding K void countPairs( int arr[], int n, int k) { // Sort the array in ascending order sort(arr, arr + n); // Store the required result int ans = 0; // Traverse the array for ( int i = 0; i < n - 1; i++) { // Store the upper bound for // the current array element int high = upper_bound(arr, arr + n, k * arr[i]) - arr; // Update the number of pairs ans += high - i - 1; } // Print the result cout << ans; } // Driver Code int main() { // Given array, arr[] int arr[] = { 2, 3, 9, 5 }; // Store the size of the array int n = sizeof (arr) / sizeof (arr[0]); int k = 2; countPairs(arr, n, k); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ public static int upper_bound( int arr[], int key) { int l = - 1 , r = arr.length; while (l + 1 < r) { int m = (l + r) >>> 1 ; if (arr[m] <= key) l = m; else r = m; } return l + 1 ; } // Function to count the number // having quotient of division // of larger element by the smaller // element in the pair not exceeding K static void countPairs( int arr[], int n, int k) { // Sort the array in ascending order Arrays.sort(arr); // Store the required result int ans = 0 ; // Traverse the array for ( int i = 0 ; i < n - 1 ; i++) { // Store the upper bound for // the current array element int high = upper_bound(arr, k * arr[i]); // Update the number of pairs ans += high - i - 1 ; } // Print the result System.out.println(ans); } // Driver Code public static void main(String[] args) { // Given array, arr[] int arr[] = { 2 , 3 , 9 , 5 }; // Store the size of the array int n = arr.length; int k = 2 ; countPairs(arr, n, k); } } // This code is contributed by Kingash |
Python3
# Python3 program for the above approach from bisect import bisect_right # Function to count the number # having quotient of division # of larger element by the smaller # element in the pair not exceeding K def countPairs(arr, n, k) : # Sort the array in ascending order arr.sort() # Store the required result ans = 0 # Traverse the array for i in range (n - 1 ): # Store the upper bound for # the current array element high = bisect_right(arr, k * arr[i]) # Update the number of pairs ans + = high - i - 1 # Print result print (ans) # Driver Code # Given array, arr[] arr = [ 2 , 3 , 9 , 5 ] # Store the size of the array n = len (arr) k = 2 countPairs(arr, n, k) # This code is contributed by sanjoy_62. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { static int upper_bound( int []arr, int key) { int l = -1, r = arr.Length; while (l + 1 < r) { int m = (l + r) >> 1; if (arr[m] <= key) l = m; else r = m; } return l + 1; } // Function to count the number // having quotient of division // of larger element by the smaller // element in the pair not exceeding K static void countPairs( int []arr, int n, int k) { // Sort the array in ascending order Array.Sort(arr); // Store the required result int ans = 0; // Traverse the array for ( int i = 0; i < n - 1; i++) { // Store the upper bound for // the current array element int high = upper_bound(arr, k * arr[i]); // Update the number of pairs ans += high - i - 1; } // Print the result Console.WriteLine(ans); } // Driver Code public static void Main() { // Given array, arr[] int []arr = { 2, 3, 9, 5 }; // Store the size of the array int n = arr.Length; int k = 2; countPairs(arr, n, k); } } // This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // Javascript program for the above approach 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 to count the number // having quotient of division // of larger element by the smaller // element in the pair not exceeding K function countPairs(arr, n, k) { // Sort the array in ascending order arr.sort(); // Store the required result let ans = 0; // Traverse the array for (let i = 0; i < n - 1; i++) { // Store the upper bound for // the current array element let high = upper_bound(arr, k * arr[i]); // Update the number of pairs ans += high - i - 1; } // Print the result document.write(ans); } // Driver code // Given array, arr[] let arr = [ 2, 3, 9, 5 ]; // Store the size of the array let n = arr.length; let k = 2; countPairs(arr, n, k); // This code is contributed by target_2 </script> |
3
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Contact Us