1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Implementation in C++
2.1.1.
Complexity Analysis
3.
Optimal Approach
3.1.
Implementation in C++
3.1.1.
Complexity Analysis
4.
FAQs
5.
Key takeaways
Last Updated: Mar 27, 2024

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

## 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

1. As we can see that a will always lie in the range [1, N].
2. Similarly, b will lie in the range [a, N] and c will lie in the range [b, N].
3. 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 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

1. 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)].
2. Similarly, b will lie in the range [a, square-root(N/a)].
3. Similarly, c will lie in the range [b, N/(a*b)]. Therefore the count c would be the numbers present in this range.
4. 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 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

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

2. 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.

3. 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.

Live masterclass