Count pairs from a given array whose product lies in a given range

0 0 10 minutes read

Given an array arr[] of size N, and integers L and R, the task is to count the number of pairs [arr_i, arr_j] 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);
}

Output

Time Complexity: O(N²)
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>

Output:

Time Complexity: O(NlogN)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!