# Count number of triplets (a, b, c) from first N natural numbers such that a * b + c = N

Given an integer **N**, the task is to count the triplets (**a, b, c**) from the first **N** natural numbers such that **a * b + c = N**.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:N = 3Output:3Explanation:

Triplets of the form a * b + c = N are { (1, 1, 2), (1, 2, 1), (2, 1, 1) }

Therefore, the required output is 3.

Input:N = 100Output:473

**Approach:** The problem can be solved based on the following observation:

For every possible pairs (a, b), If a * b < N, then only c exists. Therefore, count the pairs (a, b) whose product is less than N.

Follow the steps below to solve the problem:

- Initialize a variable, say
**cntTriplets**, to store the count of triplets of first**N**natural numbers that satisfy the given condition. - Iterate over the range
**[1, N – 1]**using variable**i**and check if**N % i == 0**or not. If found to be true, then update**cntTriplets += (N / i) – 1**. - Otherwise, update
**cntTriplets += (N / i).** - Finally, print the value of
**cntTriplets**.

Below is the implementation of the above approach.

## C++

`// C++ program to implement` `// the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the count of` `// triplets (a, b, c) with a * b + c = N` `int` `findCntTriplet(` `int` `N)` `{` ` ` `// Stores count of triplets of 1st` ` ` `// N natural numbers which are of` ` ` `// the form a * b + c = N` ` ` `int` `cntTriplet = 0;` ` ` `// Iterate over the range [1, N]` ` ` `for` `(` `int` `i = 1; i < N; i++) {` ` ` `// If N is divisible by i` ` ` `if` `(N % i != 0) {` ` ` `// Update cntTriplet` ` ` `cntTriplet += N / i;` ` ` `}` ` ` `else` `{` ` ` `// Update cntTriplet` ` ` `cntTriplet += (N / i) - 1;` ` ` `}` ` ` `}` ` ` `return` `cntTriplet;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 3;` ` ` `cout << findCntTriplet(N);` ` ` `return` `0;` `}` |

## Java

`// Java program to implement` `// the above approach` `import` `java.util.*;` `class` `GFG` `{` ` ` `// Function to find the count of` ` ` `// triplets (a, b, c) with a * b + c = N` ` ` `static` `int` `findCntTriplet(` `int` `N)` ` ` `{` ` ` `// Stores count of triplets of 1st` ` ` `// N natural numbers which are of` ` ` `// the form a * b + c = N` ` ` `int` `cntTriplet = ` `0` `;` ` ` `// Iterate over the range [1, N]` ` ` `for` `(` `int` `i = ` `1` `; i < N; i++)` ` ` `{` ` ` `// If N is divisible by i` ` ` `if` `(N % i != ` `0` `)` ` ` `{` ` ` `// Update cntTriplet` ` ` `cntTriplet += N / i;` ` ` `}` ` ` `else` ` ` `{` ` ` `// Update cntTriplet` ` ` `cntTriplet += (N / i) - ` `1` `;` ` ` `}` ` ` `}` ` ` `return` `cntTriplet;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `N = ` `3` `;` ` ` `System.out.println(findCntTriplet(N));` ` ` `}` `}` `// This code is contributed by susmitakundugoaldanga` |

## Python3

`# Python program to implement` `# the above approach` `# Function to find the count of` `# triplets (a, b, c) with a * b + c = N` `def` `findCntTriplet(N):` ` ` ` ` `# Stores count of triplets of 1st` ` ` `# N natural numbers which are of` ` ` `# the form a * b + c = N` ` ` `cntTriplet ` `=` `0` `;` ` ` `# Iterate over the range [1, N]` ` ` `for` `i ` `in` `range` `(` `1` `, N):` ` ` `# If N is divisible by i` ` ` `if` `(N ` `%` `i !` `=` `0` `):` ` ` `# Update cntTriplet` ` ` `cntTriplet ` `+` `=` `N ` `/` `/` `i;` ` ` `else` `:` ` ` `# Update cntTriplet` ` ` `cntTriplet ` `+` `=` `(N ` `/` `/` `i) ` `-` `1` `;` ` ` `return` `cntTriplet;` `# Driver code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `N ` `=` `3` `;` ` ` `print` `(findCntTriplet(N));` `# This code is contributed by 29AjayKumar` |

## C#

`// C# program to implement` `// the above approach` `using` `System;` `class` `GFG` `{` ` ` `// Function to find the count of` ` ` `// triplets (a, b, c) with a * b + c = N` ` ` `static` `int` `findCntTriplet(` `int` `N)` ` ` `{` ` ` `// Stores count of triplets of 1st` ` ` `// N natural numbers which are of` ` ` `// the form a * b + c = N` ` ` `int` `cntTriplet = 0;` ` ` `// Iterate over the range [1, N]` ` ` `for` `(` `int` `i = 1; i < N; i++)` ` ` `{` ` ` `// If N is divisible by i` ` ` `if` `(N % i != 0)` ` ` `{` ` ` `// Update cntTriplet` ` ` `cntTriplet += N / i;` ` ` `}` ` ` `else` ` ` `{` ` ` `// Update cntTriplet` ` ` `cntTriplet += (N / i) - 1;` ` ` `}` ` ` `}` ` ` `return` `cntTriplet;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `Main(String[] args)` ` ` `{` ` ` `int` `N = 3;` ` ` `Console.WriteLine(findCntTriplet(N));` ` ` `}` `}` `// This code is contributed by 29AjayKumar` |

## Javascript

`<script>` `// javascript program for the above approach` ` ` ` ` `// Function to find the count of` ` ` `// triplets (a, b, c) with a * b + c = N` ` ` `function` `findCntTriplet(N)` ` ` `{` ` ` `// Stores count of triplets of 1st` ` ` `// N natural numbers which are of` ` ` `// the form a * b + c = N` ` ` `let cntTriplet = 0;` ` ` `// Iterate over the range [1, N]` ` ` `for` `(let i = 1; i < N; i++)` ` ` `{` ` ` `// If N is divisible by i` ` ` `if` `(N % i != 0)` ` ` `{` ` ` `// Update cntTriplet` ` ` `cntTriplet += Math.floor(N / i);` ` ` `}` ` ` `else` ` ` `{` ` ` `// Update cntTriplet` ` ` `cntTriplet += Math.floor(N / i) - 1;` ` ` `}` ` ` `}` ` ` `return` `cntTriplet;` ` ` `}` `// Driver Code` ` ` ` ` `let N = 3;` ` ` `document.write(findCntTriplet(N));` ` ` `</script>` |

**Output:**

3

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