Given a positive integer N, the task is to find the number of triplets (A, B, C) from the first N Natural Numbers such that A * B * C ≤ N.
Examples:
Input: N = 2
Output: 4
Explanation:
Following are the triplets that satisfy the given criteria:
- ( 1, 1, 1 ) => 1 * 1 * 1 = 1 ≤ 2.
- ( 1, 1, 2 ) => 1 * 1 * 2 = 2 ≤ 2.
- ( 1, 2, 1 ) => 1 * 2 * 1 = 2 ≤ 2.
- ( 2, 1, 1 ) => 2 * 1 * 1 = 2 ≤ 2.
Therefore, the total count of triplets is 4.
Input: N = 10
Output: 53
Naive Approach: The simplest approach to solve the given problem is to generate all possible triplets from the first N natural numbers and count those triplets that satisfy the given criteria. After checking for all the triplets, print the total count obtained.
C++
// C++ program for the above approach#include <iostream>using namespace std;int countTriplets(int n) { int count = 0; // Iterate over all possible values of i, j, and k for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) { // Check if the product of i, j, and k is less than or equal to n if (i * j * k <= n) { count++; // Increment the count if the condition is satisfied } } } } return count;}//Driver codeint main() { int N = 4; cout << countTriplets(N) << endl; return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { public static void main(String[] args) { int N = 4; System.out.println(countTriplets(N)); } public static int countTriplets(int n) { int count = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) { if (i * j * k <= n) { count++; } } } } return count; }}//This code is contributed by aeroabrar_31 |
Python3
def count_triplets(n): count = 0 # Iterate over all possible values of i, j, and k for i in range(1, n + 1): for j in range(1, n + 1): for k in range(1, n + 1): # Check if the product of i, j, and k is less than or equal to n if i * j * k <= n: count += 1 # Increment the count if the condition is satisfied return count# Driver codedef main(): N = 4 print(count_triplets(N))if __name__ == "__main__": main() |
C#
using System;class GFG{ public static void Main(string[] args) { int N = 4; Console.WriteLine(CountTriplets(N)); // Call the CountTriplets method and print the result. } public static int CountTriplets(int n) { int count = 0; // Initialize a count variable to keep track of the number of triplets. for (int i = 1; i <= n; i++) // Loop through possible values of i from 1 to n. { for (int j = 1; j <= n; j++) // Loop through possible values of j from 1 to n. { for (int k = 1; k <= n; k++) // Loop through possible values of k from 1 to n. { if (i * j * k <= n) // Check if the product of i, j, and k is less than or equal to n. { count++; // If the condition is met, increment the count. } } } } return count; // Return the final count of valid triplets. }} |
Javascript
<script> // JavaScript program for the above approach function countTriplets(n) { let count = 0; // Iterate over all possible values of i, j, and k for (let i = 1; i <= n; i++) { for (let j = 1; j <= n; j++) { for (let k = 1; k <= n; k++) { // Check if the product of i, j, and k is less than or equal to n if (i * j * k <= n) { count++; // Increment the count if the condition is satisfied } } } } return count; } // Driver code const N = 4; console.log(countTriplets(N));</script> |
Output
13
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by the observation that if A and B are fixed, then it is possible to calculate all the possible choices for C by doing N/(A*B) because N/(A*B) will give the maximum value, say X, which on multiplication with (A*B) results in a value less than or equal to N. So, all possible choices of C will be from 1 to X. Now, A and B can be fixed by trying A for every possible number till N, and B for every possible number till (N/A). Follow the steps below to solve the given problem:
- Initialize variable, say cnt as 0 that stores the count of triplets possible.
- Iterate a loop over the range [1, N] using the variable i and nested iterate over the range [1, N] using the variable j and increment the value of cnt by the value of cnt/(i*j).
- After completing the above steps, print the value of cnt as the result.
Below is the implementation of the approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find number of triplets// (A, B, C) having A * B * C <= Nint countTriplets(int N){ // Stores the count of triplets int cnt = 0; // Iterate a loop fixing the value // of A for (int A = 1; A <= N; ++A) { // Iterate a loop fixing the // value of A for (int B = 1; B <= N / A; ++B) { // Find the total count of // triplets and add it to cnt cnt += N / (A * B); } } // Return the total triplets formed return cnt;}// Driver Codeint main(){ int N = 2; cout << countTriplets(N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to find number of triplets // (A, B, C) having A * B * C <= N static int countTriplets(int N) { // Stores the count of triplets int cnt = 0; // Iterate a loop fixing the value // of A for (int A = 1; A <= N; ++A) { // Iterate a loop fixing the // value of A for (int B = 1; B <= N / A; ++B) { // Find the total count of // triplets and add it to cnt cnt += N / (A * B); } } // Return the total triplets formed return cnt; } // Driver Code public static void main(String[] args) { int N = 2; System.out.println(countTriplets(N)); }}// This code is contributed by dwivediyash |
Python3
# Python3 program for the above approach# Function to find number of triplets# (A, B, C) having A * B * C <= Ndef countTriplets(N) : # Stores the count of triplets cnt = 0; # Iterate a loop fixing the value # of A for A in range( 1, N + 1) : # Iterate a loop fixing the # value of A for B in range(1, N // A + 1) : # Find the total count of # triplets and add it to cnt cnt += N // (A * B); # Return the total triplets formed return cnt;# Driver Codeif __name__ == "__main__" : N = 2; print(countTriplets(N)); # This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;public class GFG { // Function to find number of triplets // (A, B, C) having A * B * C <= N static int countTriplets(int N) { // Stores the count of triplets int cnt = 0; // Iterate a loop fixing the value // of A for (int A = 1; A <= N; ++A) { // Iterate a loop fixing the // value of A for (int B = 1; B <= N / A; ++B) { // Find the total count of // triplets and add it to cnt cnt += N / (A * B); } } // Return the total triplets formed return cnt; } // Driver Code public static void Main(string[] args) { int N = 2; Console.WriteLine(countTriplets(N)); }}// This code is contributed by AnkThon |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find number of triplets // (A, B, C) having A * B * C <= N function countTriplets(N) { // Stores the count of triplets let cnt = 0; // Iterate a loop fixing the value // of A for (let A = 1; A <= N; ++A) { // Iterate a loop fixing the // value of A for (let B = 1; B <= N / A; ++B) { // Find the total count of // triplets and add it to cnt cnt += N / (A * B); } } // Return the total triplets formed return cnt; } // Driver Code let N = 2; document.write(countTriplets(N));// This code is contributed by Potta Lokesh </script> |
Output
4
Time Complexity: O(N * log N)
Auxiliary Space: O(1)
