Count ordered pairs with product less than N

0 0 4 minutes read

Given an integer N. The task is to count the number of ordered pairs (a, b) such that $a * b < N$ .
Examples:

Input: N = 5
Output: 8
Ordered Pairs are = (1, 1), (1, 2), (1, 3),
(1, 4), (2, 1), (2, 2), (3, 1), (4, 1).

Input: N = 1000
Output: 7053

Naive Approach: Run two for loops upto N – 1 and count ordered pairs whose products are less than N.

Efficient Approach: Let’s considered an ordered pair (a, b). Then, if the product of two numbers is less than n i:e a * b < n, then at least one of them must be less than square root of n. We can prove by contradiction that if both numbers are greater than the square root of n then their product is not less than n.

So, you can take all integers up to sqrt(n – 1) instead of all integers up to n. For each a, count the number of b >= a such that a * b < n. Then multiply the result by two to count the pair (b, a) for each pair (a, b) you saw. After that, subtract the integer part of sqrt(n – 1) to ensure the pairs (a, a) were counted exactly once.

Below is the implementation of the above approach:

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return count of Ordered pairs
// whose product are less than N
int countOrderedPairs(int N)
{
    // Initialize count to 0
    int count_pairs = 0;
 
    // count total pairs
    for (int i = 1; i <= sqrt(N - 1); ++i) {
        for (int j = i; j * i < N; ++j)
            ++count_pairs;
    }
 
    // multiply by 2 to get ordered_pairs
    count_pairs *= 2;
 
    // subtract redundant pairs (a, b) where a==b.
    count_pairs -= int(sqrt(N - 1));
 
    // return answer
    return count_pairs;
}
 
// Driver code
int main()
{
    int N = 5;
 
    // function call to print required answer
    cout << countOrderedPairs(N);
 
    return 0;
}

Java

// Java implementation of above approach
 
class GFG{
// Function to return count of Ordered pairs
// whose product are less than N
static int countOrderedPairs(int N)
{
    // Initialize count to 0
    int count_pairs = 0;
 
    // count total pairs
    for (int i = 1; i <= (int)Math.sqrt(N - 1); ++i) {
        for (int j = i; j * i < N; ++j)
            ++count_pairs;
    }
 
    // multiply by 2 to get ordered_pairs
    count_pairs *= 2;
 
    // subtract redundant pairs (a, b) where a==b.
    count_pairs -= (int)(Math.sqrt(N - 1));
 
    // return answer
    return count_pairs;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 5;
 
    // function call to print required answer
    System.out.println(countOrderedPairs(N));
}
}
// This code is contributed by mits

Python3

# Python3 implementation of above approach
 
from math import sqrt
# Function to return count of Ordered pairs
# whose product are less than N
def countOrderedPairs(N):
    # Initialize count to 0
    count_pairs = 0
 
    # count total pairs
    p = int(sqrt(N-1)) + 1
    q = int(sqrt(N))+2
    for i in range(1,p,1):
        for j in range(i,q,1):
            count_pairs += 1
     
    # multiply by 2 to get ordered_pairs
    count_pairs *= 2
 
    # subtract redundant pairs (a, b) where a==b.
    count_pairs -= int(sqrt(N - 1))
 
    # return answer
    return count_pairs
 
# Driver code
if __name__ == '__main__':
    N = 5
 
    # function call to print required answer
    print(countOrderedPairs(N))
 
# This code is contributed by
# Surendra_Gangwar

C#

//C# implementation of above approach 
 
using System;
 
public class GFG{
    // Function to return count of Ordered pairs 
// whose product are less than N 
static int countOrderedPairs(int N) 
{ 
    // Initialize count to 0 
    int count_pairs = 0; 
 
    // count total pairs 
    for (int i = 1; i <= (int)Math.Sqrt(N - 1); ++i) { 
        for (int j = i; j * i < N; ++j) 
            ++count_pairs; 
    } 
 
    // multiply by 2 to get ordered_pairs 
    count_pairs *= 2; 
 
    // subtract redundant pairs (a, b) where a==b. 
    count_pairs -= (int)(Math.Sqrt(N - 1)); 
 
    // return answer 
    return count_pairs; 
} 
 
// Driver code 
    static public void Main (){
     
    int N = 5; 
    // function call to print required answer 
    Console.WriteLine(countOrderedPairs(N)); 
} 
} 
// This code is contributed by Sachin.

PHP

<?php
// PHP implementation of above approach 
 
// Function to return count of Ordered 
// pairs whose products are less than N 
function countOrderedPairs($N) 
{ 
    // Initialize count to 0 
    $count_pairs = 0; 
 
    // count total pairs 
    for ($i = 1; $i <= sqrt($N - 1); ++$i) 
    { 
        for ( $j = $i; $j * $i < $N; ++$j) 
            ++$count_pairs; 
    } 
 
    // multiply by 2 to get ordered_pairs 
    $count_pairs *= 2; 
 
    // subtract redundant pairs 
    // (a, b) where a==b. 
    $count_pairs -= (sqrt($N - 1)); 
 
    // return answer 
    return $count_pairs; 
} 
 
// Driver code 
$N = 5; 
 
// function call to print
// required answer 
echo countOrderedPairs($N); 
 
// This code is contributed
// by Sach_Code
?>

Javascript

<script>
//Javascript implementation of above approach
 
// Function to return count of Ordered pairs
// whose product are less than N
function countOrderedPairs( N)
{
    // Initialize count to 0
    var count_pairs = 0;
 
    // count total pairs
    for (var i = 1; i <= Math.sqrt(N - 1); ++i) {
        for (var j = i; j * i < N; ++j)
            ++count_pairs;
    }
 
    // multiply by 2 to get ordered_pairs
    count_pairs *= 2;
 
    // subtract redundant pairs (a, b) where a==b.
    count_pairs -= parseInt(Math.sqrt(N - 1));
 
    // return answer
    return count_pairs;
}
 
var N = 5;
 // function call to print required answer
document.write( countOrderedPairs(N));
 
// This code is contributed by SoumikMondal
</script>

Output:

Time Complexity: O(N*sqrt(N)), 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!