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