Triplets are set of three numbers for example {1, 2, 3} is considered as a triplet.

What does the sqrt function in C++ do?

The sqrt function in C++ calculates the square root of a number in C++ and it gives the floor value of the exact square root. For example, the square root of 8 is 2.828 but if we do sqrt(8) it will give us 2 as the answer because the ceil value of 2.8 is 2.

What is space complexity of an algorithm?

Space complexity can be referred to as the extra space used by the algorithm to solve a particular problem.

Table of contents

Introduction

1.1.

Problem Statement

1.2.

Sample Examples

Brute Force Approach

2.1.

Implementation in C++

2.1.1.

Complexity Analysis

Optimal Approach

3.1.

Implementation in C++

3.1.1.

Complexity Analysis

FAQs

Key takeaways

Last Updated: Mar 27, 2024

Count of sorted triplets (a, b, c) whose product is at most equal to N

Author Vibhor Bhatnagar

Introduction

This blog will discuss the solution to this problem to count of sorted triplets (a, b, c) whose product is at most equal to N.

Problem Statement

We are given an integer N, and our task is to find the count of triplets (a, b, c) such that a<=b<=c and a*b*c <=N.So before we deep dive into the answer, we should look at some examples to understand the problem better.

Sample Examples

Example 1:

Input:
N = 4

Output: 
5

Explanation:
The required triplets are (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2). Hence the count of triplets is 5.

Example 2:

Input:
N = 14 

Output:
24

Also see, Euclid GCD Algorithm

Brute Force Approach

As we can see that a will always lie in the range [1, N].
Similarly, b will lie in the range [a, N] and c will lie in the range [b, N].
Therefore, for fixed values of a and b, we will take the product of a, b, and c for every value of c and if the product is less than or equal to N then we will increment the answer.

Implementation in C++

// C++ code to find the Count of sorted triplets (a, b, c) whose product is at most equal to N
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll int countTriplets(ll int N)
{
    // to store the count of triplets
    ll int ans = 0;

    // loop to iterate in the range [1, N]
    for (ll int a = 1; a <= N; a++)
    {
        // loop to iterate in the range [a, N]
        for (ll int b = a; b <= N; b++)
        {
            ll int x = a * b;
            // loop to iterate in the range [b, N]
            for (ll int c = b; c <= N; c++)
            {
                x *= c;
                if (x <= N)
                {
                    ans++;
                }
                x /= c;
            }
        }
    }

    // Return Answer
    return ans;
}

// Driver Code
int main()
{
    int N = 4;
    cout << countTriplets(N);

    return 0;
}

Output:

Input: N = 7
Output: 9

Complexity Analysis

Time Complexity: O(N³)

Since we are using three nested for loop in this approach therefore the time complexity will be O(N³)

Space Complexity: O(1)

Since we are not using any extra space, therefore the space complexity will be O(N).

Optimal Approach

To solve this problem, to find the count of sorted triplets (a, b, c) whose product is at most N, Now as we can see, a will always lie in the range of [1, cube-root(N)].
Similarly, b will lie in the range [a, square-root(N/a)].
Similarly, c will lie in the range [b, N/(a*b)]. Therefore the count c would be the numbers present in this range.
Therefore for fixed values of a and b, the possible values of c would be

N/(a*b) - b + 1.

Implementation in C++

// C++ code to find the Count of sorted triplets (a, b, c) whose product is at most equal to N
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll int countTriplets(ll int N)
{
    // to store the count of triplets
    ll int ans = 0;

    // loop to iterate in the range [1, cubrt(N)]
    for (ll int a = 1; a <= cbrt(N); a++)
    {
        // loop to iterate in the range [a, sqrt(N/a)]
        for (ll int b = a; b <= sqrt(N / a); b++)
        {
            // to add the count of values of c for fixed values of a and b
            ans += N / a / b - b + 1;
        }
    }

    // Return Answer
    return ans;
}

// Driver Code to find the count of sorted triplets (a, b, c) whose product is at most equal to N
int main()
{
    int N = 10;
    cout << countTriplets(N);

    return 0;
}

Output:

Input: N = 10
Output: 16

Complexity Analysis

Time Complexity: O(N²ˡ³)

Since we are traveling from [1, cube-root(N)] and the inner loop is also traveling from [a, sqrt(N/a)], therefore, the time complexity will be the square of the cube root of N.

Space Complexity: O(1), since we are not using any extra space, therefore the space complexity will be O(N).

FAQs

What is a triplet?
Triplets are set of three numbers for example {1, 2, 3} is considered as a triplet.
What does the sqrt function in C++ do?
The sqrt function in C++ calculates the square root of a number in C++ and it gives the floor value of the exact square root. For example, the square root of 8 is 2.828 but if we do sqrt(8) it will give us 2 as the answer because the ceil value of 2.8 is 2.
What is space complexity of an algorithm?
Space complexity can be referred to as the extra space used by the algorithm to solve a particular problem.

Key takeaways

In this article, we discussed the problem find the Count of sorted triplets (a, b, c) whose product is at most equal to N. We have discussed its approach, and we have also discussed the time and space complexities of the approach.

Until then, Keep Learning and Keep Coding.