Count of triplets till N whose product is at most N - Coding

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 code
int 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 code
def 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

Time Complexity: O(N³)
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 <= N
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
int main()
{
    int N = 2;
    cout << countTriplets(N);
 
    return 0;
}

Java

// Java program for the above approach
import 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 <= N
def 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 Code
if __name__ == "__main__" :
 
    N = 2;
    print(countTriplets(N));
 
    # This code is contributed by AnkThon

C#

// C# program for the above approach
using 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

Time Complexity: O(N * log N)
Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

Mathematical

Related
Count of Unique Direct Path Between N Points On a Plane
Check if elements of given array can be rearranged such that (arr[i] + i*K) % N = i for all values of i in range [0, N-1]
Count of distinct integers belonging to first N terms of at least one of given GPs
Minimize arithmetic operations to be performed on adjacent elements of given Array to reduce it
Maximize sum of profits for N items such that profit for ith item is product of its weight and count of distinct chosen values

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	7