Count pairs from a given array whose product lies in a given range
Given an array arr[] of size N, and integers L and R, the task is to count the number of pairs [arri , arrj] such that i < j and the product of arr[i] * arr[j] lies in the given range [L, R], i.e. L ? arr[i] * arr[j] ? R.
Examples:
Input: arr[ ] = {4, 1, 2, 5}, L = 4, R = 9
Output: 3
Explanation: Valid pairs are {4, 1}, {1, 5} and {4, 2}.Input: arr[ ] = {1, 2, 5, 10, 5}, L = 2, R = 15
Output: 6
Explanation: Valid pairs are {1, 2}, {1, 5}, {1, 10}, {1, 5}, {2, 5}, {2, 5}.
Naive Approach: The simplest approach to solve the problem is to generate all possible pairs from the array and for each pair, check if its product lies in the range [L, R] or not.
C++
#include <bits/stdc++.h> using namespace std; // Function to Count pairs from a given array // whose product lies in a given range int countPairs( int arr[], int L, int R, int N) { // Variable to store the count int count = 0; // Iterating through the array and // counting all pairs whose product // is in the range for ( int i = 0; i < N; i++) { for ( int j = i + 1; j < N; j++) { // Condition if (arr[i]*arr[j] >= L && arr[i]*arr[j] <= R) { count++; } } } // Print the count cout<<count<<endl; } // Driver Code int main() { // Given Input int arr[] = { 4, 1, 2, 5 }; int l = 4, r = 9; int n = sizeof (arr) / sizeof (arr[0]); // Function Call countPairs(arr, l, r, n); return 0; } // This code is contributed Pushpesh Raj |
Java
// Java code for above approach import java.io.*; class GFG { // Function to Count pairs from a given array // whose product lies in a given range static void countPairs( int arr[], int L, int R, int N) { // Variable to store the count int count = 0 ; // Iterating through the array and // counting all pairs whose product // is in the range for ( int i = 0 ; i < N; i++) { for ( int j = i + 1 ; j < N; j++) { // Condition if (arr[i]*arr[j] >= L && arr[i]*arr[j] <= R) { count++; } } } // Print the count System.out.println(count); } // Driver Code public static void main (String[] args) { // Given Input int arr[] = { 4 , 1 , 2 , 5 }; int l = 4 , r = 9 ; int n = arr.length; // Function Call countPairs(arr, l, r, n); } } // This code is contributed Utkarsh Kumar. |
Python3
# Python code # Function to Count pairs from a given array # whose product lies in a given range def countPairs(arr, L, R, N): # Variable to store the count count = 0 # Iterating through the array and # counting all pairs whose product # is in the range for i in range (N): for j in range (i + 1 , N): # Condition if (arr[i] * arr[j] > = L and arr[i] * arr[j] < = R): count + = 1 # Print the count print (count) # Driver Code if __name__ = = "__main__" : # Given Input arr = [ 4 , 1 , 2 , 5 ] l = 4 r = 9 N = len (arr) # Function Call countPairs(arr, l, r, N) |
C#
using System; class GFG { // Function to Count pairs from a given array whose // product lies in a given range static void countPairs( int [] arr, int L, int R, int N) { // Variable to store the count int count = 0; // Iterating through the array and counting all pairs // whose product is in the range for ( int i = 0; i < N; i++) { for ( int j = i + 1; j < N; j++) { // Condition if (arr[i] * arr[j] >= L && arr[i] * arr[j] <= R) { count++; } } } // Print the count Console.WriteLine(count); } public static void Main() { // Given Input int [] arr = { 4, 1, 2, 5 }; int l = 4; int r = 9; int n = arr.Length; // Function Call countPairs(arr, l, r, n); } } |
Javascript
// Function to Count pairs from a given array // whose product lies in a given range function countPairs(arr, L, R, N) { // Variable to store the count let count = 0; // Iterating through the array and // counting all pairs whose product // is in the range for (let i = 0; i < N; i++) { for (let j = i + 1; j < N; j++) { // Condition if (arr[i]*arr[j] >= L && arr[i]*arr[j] <= R) { count += 1; } } } // Print the count console.log(count); } // Driver Code if ( true ) { // Given Input let arr = [ 4, 1, 2, 5 ]; let l = 4; let r = 9; let N = arr.length; // Function Call countPairs(arr, l, r, N); } |
3
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: This problem can be solved by Sorting and Binary Search technique. Follow the steps below to solve this problem:
- Sort the array arr[].
- Initialize a variable, say ans as 0, to store the number of pairs whose product lies in the range [L, R].
- Iterate over the range [0, N-1] using a variable i and perform the following steps:
- Find upper bound of an element such that the element is less than equal to R / arr[i].
- Find lower bound of an element such that the element is greater than or equal to L / arr[i].
- Add upper bound – lower bound to ans
- After completing the above steps, print ans.
Below is the implementation of the above approach.
C++
#include<bits/stdc++.h> using namespace std; // Function to count pairs from an array whose product lies in the range [l, r] int countPairs(vector< int > arr, int l, int r, int n) { // Sort the array arr[] sort(arr.begin(), arr.end()); // Stores the final answer int ans = 0; for ( int i = 0; i < n; i++) { // Upper Bound for arr[j] such that arr[j] <= r/arr[i] auto itr1 = upper_bound(arr.begin(), arr.end(), r / arr[i]); // Lower Bound for arr[j] such that arr[j] >= l/arr[i] auto itr2 = lower_bound(arr.begin(), arr.end(), (l + arr[i] - 1) / arr[i]); ans += max(0, ( int )(itr1 - itr2) - (arr[i] * arr[i] >= l && arr[i] * arr[i] <= r)); } // Return the answer return ans / 2; } // Driver Code int main() { // Given Input vector< int > arr = {4, 1, 2, 5}; int l = 4; int r = 9; int n = arr.size(); // Function Call cout << countPairs(arr, l, r, n) << endl; return 0; } |
Java
// Java program for above approach import java.util.Arrays; class GFG{ // Function to count pairs from an array // whose product lies in the range [l, r] public static void countPairs( int [] arr, int l, int r, int n) { // Sort the array arr[] Arrays.sort(arr); // Stores the final answer int ans = 0 ; for ( int i = 0 ; i < n; i++) { // Upper Bound for arr[j] such // that arr[j] <= r/arr[i] int itr1 = upper_bound(arr, 0 , arr.length - 1 , l / arr[i]); // Lower Bound for arr[j] such // that arr[j] >= l/arr[i] int itr2 = lower_bound(arr, 0 , arr.length - 1 , l / arr[i]); ans += itr1 - itr2; } // Print the answer System.out.println(ans); } public static int lower_bound( int [] arr, int low, int high, int X) { // Base Case if (low > high) { return low; } // Find the middle index int mid = low + (high - low) / 2 ; // If arr[mid] is greater than // or equal to X then search // in left subarray if (arr[mid] >= X) { return lower_bound(arr, low, mid - 1 , X); } // If arr[mid] is less than X // then search in right subarray return lower_bound(arr, mid + 1 , high, X); } public static int upper_bound( int [] arr, int low, int high, int X) { // Base Case if (low > high) return low; // Find the middle index int mid = low + (high - low) / 2 ; // If arr[mid] is less than // or equal to X search in // right subarray if (arr[mid] <= X) { return upper_bound(arr, mid + 1 , high, X); } // If arr[mid] is greater than X // then search in left subarray return upper_bound(arr, low, mid - 1 , X); } // Driver Code public static void main(String args[]) { // Given Input int [] arr = { 4 , 1 , 2 , 5 }; int l = 4 , r = 9 ; int n = arr.length; // Function Call countPairs(arr, l, r, n); } } // This code is contributed by gfgking. |
Python3
# Python program for above approach # Function to count pairs from an array # whose product lies in the range [l, r] def countPairs(arr, l, r, n): # Sort the array arr[] arr[:: - 1 ] # Stores the final answer ans = 0 ; for i in range (n): # Upper Bound for arr[j] such # that arr[j] <= r/arr[i] itr1 = upper_bound(arr, 0 , len (arr) - 1 , l / / arr[i]) # Lower Bound for arr[j] such # that arr[j] >= l/arr[i] itr2 = lower_bound(arr, 0 , len (arr) - 1 , l / / arr[i]); ans + = itr1 - itr2; # Print the answer print (ans); def lower_bound(arr, low, high, X): # Base Case if (low > high): return low; # Find the middle index mid = low + (high - low) / / 2 ; # If arr[mid] is greater than # or equal to X then search # in left subarray if (arr[mid] > = X): return lower_bound(arr, low, mid - 1 , X); # If arr[mid] is less than X # then search in right subarray return lower_bound(arr, mid + 1 , high, X); def upper_bound(arr, low, high, X): # Base Case if (low > high): return low; # Find the middle index mid = low + (high - low) / / 2 ; # If arr[mid] is less than # or equal to X search in # right subarray if (arr[mid] < = X): return upper_bound(arr, mid + 1 , high, X); # If arr[mid] is greater than X # then search in left subarray return upper_bound(arr, low, mid - 1 , X); # Driver Code # Given Input arr = [ 4 , 1 , 2 , 5 ]; l = 4 ; r = 9 ; n = len (arr) # Function Call countPairs(arr, l, r, n); # This code is contributed by _Saurabh_Jaiswal. |
C#
// C# program for the above approach using System; class GFG{ // Function to count pairs from an array // whose product lies in the range [l, r] public static void countPairs( int [] arr, int l, int r, int n) { // Sort the array arr[] Array.Sort(arr); // Stores the final answer int ans = 0; for ( int i = 0; i < n; i++) { // Upper Bound for arr[j] such // that arr[j] <= r/arr[i] int itr1 = upper_bound(arr, 0, arr.Length - 1, l / arr[i]); // Lower Bound for arr[j] such // that arr[j] >= l/arr[i] int itr2 = lower_bound(arr, 0, arr.Length - 1, l / arr[i]); ans += itr1 - itr2; } // Print the answer Console.WriteLine(ans); } public static int lower_bound( int [] arr, int low, int high, int X) { // Base Case if (low > high) { return low; } // Find the middle index int mid = low + (high - low) / 2; // If arr[mid] is greater than // or equal to X then search // in left subarray if (arr[mid] >= X) { return lower_bound(arr, low, mid - 1, X); } // If arr[mid] is less than X // then search in right subarray return lower_bound(arr, mid + 1, high, X); } public static int upper_bound( int [] arr, int low, int high, int X) { // Base Case if (low > high) return low; // Find the middle index int mid = low + (high - low) / 2; // If arr[mid] is less than // or equal to X search in // right subarray if (arr[mid] <= X) { return upper_bound(arr, mid + 1, high, X); } // If arr[mid] is greater than X // then search in left subarray return upper_bound(arr, low, mid - 1, X); } // Driver code public static void Main( string [] args) { // Given Input int [] arr = { 4, 1, 2, 5 }; int l = 4, r = 9; int n = arr.Length; // Function Call countPairs(arr, l, r, n); } } // This code is contributed by sanjoy_62 |
Javascript
<script> // Javascript program for above approach // Function to count pairs from an array // whose product lies in the range [l, r] function countPairs(arr, l, r, n) { // Sort the array arr[] arr.sort((a, b) => a - b); // Stores the final answer let ans = 0; for (let i = 0; i < n; i++) { // Upper Bound for arr[j] such // that arr[j] <= r/arr[i] let itr1 = upper_bound(arr, 0, arr.length - 1, Math.floor(l / arr[i])); // Lower Bound for arr[j] such // that arr[j] >= l/arr[i] let itr2 = lower_bound(arr, 0, arr.length - 1, Math.floor(l / arr[i])); ans += itr1 - itr2; } // Print the answer document.write(ans + "<br>" ); } function lower_bound(arr, low, high, X) { // Base Case if (low > high) { return low; } // Find the middle index let mid = Math.floor(low + (high - low) / 2); // If arr[mid] is greater than // or equal to X then search // in left subarray if (arr[mid] >= X) { return lower_bound(arr, low, mid - 1, X); } // If arr[mid] is less than X // then search in right subarray return lower_bound(arr, mid + 1, high, X); } function upper_bound(arr, low, high, X) { // Base Case if (low > high) return low; // Find the middle index let mid = Math.floor(low + (high - low) / 2); // If arr[mid] is less than // or equal to X search in // right subarray if (arr[mid] <= X) { return upper_bound(arr, mid + 1, high, X); } // If arr[mid] is greater than X // then search in left subarray return upper_bound(arr, low, mid - 1, X); } // Driver Code // Given Input let arr = [4, 1, 2, 5]; let l = 4, r = 9; let n = arr.length // Function Call countPairs(arr, l, r, n); // This code is contributed by gfgking. </script> |
3
Time Complexity: O(NlogN)
Auxiliary Space: O(1)