Given an integer N. The task is to count the number of ordered pairs (a, b) such that 
.
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 Nint 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 codeint main(){ int N = 5; // function call to print required answer cout << countOrderedPairs(N); return 0;} |
Java
// Java implementation of above approachclass GFG{// Function to return count of Ordered pairs// whose product are less than Nstatic 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 codepublic 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 approachfrom math import sqrt# Function to return count of Ordered pairs# whose product are less than Ndef 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 codeif __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 Nfunction 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 answerdocument.write( countOrderedPairs(N));// This code is contributed by SoumikMondal</script> |
Output:
8
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
