# Find the Nth term divisible by a or b or c

Given four integers **a**, **b**, **c**, and **N**. The task is to find the **N ^{th}** term which is divisible by either of

**a**,

**b**or

**c**.

**Examples:**

Input:a = 2, b = 3, c = 5, N = 10Output:14

Sequence is 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16…Input:a = 3, b = 5, c = 7, N = 10Output:18

**Naive Approach:** A simple approach is to traverse over all the terms starting from **1** until we find the desired **N ^{th}** term which is divisible by either

**a**,

**b**or

**c**. This solution has time complexity of O(N).

**Efficient Approach:**The idea is to use Binary search. Here we can calculate how many numbers from

**1**to

**num**are divisible by either

**a**,

**b**or

**c**by using the formula:

**(num / a) + (num / b) + (num / c) – (num / lcm(a, b)) – (num / lcm(b, c)) – (num / lcm(a, c)) + (num / lcm(a, b, c))**

The above formula is derived using set theory

Below is the implementation of the above approach:

## C++

`// C++ implementation of the approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to return` `// gcd of a and b` `int` `gcd(` `int` `a, ` `int` `b)` `{` ` ` `if` `(a == 0)` ` ` `return` `b;` ` ` `return` `gcd(b % a, a);` `}` `// Function to return the lcm of a and b` `int` `lcm(` `int` `a, ` `int` `b)` `{` ` ` `return` `(a * b) / gcd(a, b);` `}` `// Function to return the count of numbers` `// from 1 to num which are divisible by a, b or c` `int` `divTermCount(` `int` `a, ` `int` `b, ` `int` `c, ` `int` `num)` `{` ` ` `// Calculate number of terms divisible by a and` ` ` `// by b and by c then, remove the terms which is are` ` ` `// divisible by both a and b, both b and c, both` ` ` `// c and a and then add which are divisible by a and` ` ` `// b and c` ` ` `return` `((num / a) + (num / b) + (num / c)` ` ` `- (num / lcm(a, b))` ` ` `- (num / lcm(b, c))` ` ` `- (num / lcm(a, c))` ` ` `+ (num / lcm(a, lcm(b, c))));` `}` `// Function to find the nth term` `// divisible by a, b or c` `// by using binary search` `int` `findNthTerm(` `int` `a, ` `int` `b, ` `int` `c, ` `int` `n)` `{` ` ` `// Set low to 1 and high to max (a, b, c) * n` ` ` `int` `low = 1, high = INT_MAX, mid;` ` ` `while` `(low < high) {` ` ` `mid = low + (high - low) / 2;` ` ` `// If the current term is less than` ` ` `// n then we need to increase low` ` ` `// to mid + 1` ` ` `if` `(divTermCount(a, b, c, mid) < n)` ` ` `low = mid + 1;` ` ` `// If current term is greater than equal to` ` ` `// n then high = mid` ` ` `else` ` ` `high = mid;` ` ` `}` ` ` `return` `low;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `a = 2, b = 3, c = 5, n = 10;` ` ` `cout << findNthTerm(a, b, c, n);` ` ` `return` `0;` `}` |

## Java

`// Java implementation of the approach` `class` `GFG` `{` ` ` ` ` `// Function to return` ` ` `// gcd of a and b` ` ` `static` `int` `gcd(` `int` `a, ` `int` `b)` ` ` `{` ` ` `if` `(a == ` `0` `)` ` ` `return` `b;` ` ` ` ` `return` `gcd(b % a, a);` ` ` `}` ` ` `// Function to return the lcm of a and b` ` ` `static` `int` `lcm(` `int` `a, ` `int` `b)` ` ` `{` ` ` `return` `(a * b) / gcd(a, b);` ` ` `}` ` ` `// Function to return the count of numbers` ` ` `// from 1 to num which are divisible by a, b or c` ` ` `static` `int` `divTermCount(` `int` `a, ` `int` `b, ` `int` `c, ` `int` `num)` ` ` `{` ` ` `// Calculate number of terms divisible by a and` ` ` `// by b and by c then, remove the terms which is are` ` ` `// divisible by both a and b, both b and c, both` ` ` `// c and a and then add which are divisible by a and` ` ` `// b and c` ` ` `return` `((num / a) + (num / b) + (num / c)` ` ` `- (num / lcm(a, b))` ` ` `- (num / lcm(b, c))` ` ` `- (num / lcm(a, c))` ` ` `+ (num / lcm(a, lcm(b, c))));` ` ` `}` ` ` `// Function to find the nth term` ` ` `// divisible by a, b or c` ` ` `// by using binary search` ` ` `static` `int` `findNthTerm(` `int` `a, ` `int` `b, ` `int` `c, ` `int` `n)` ` ` `{` ` ` `// Set low to 1 and high to max (a, b, c) * n` ` ` `int` `low = ` `1` `, high = Integer.MAX_VALUE, mid;` ` ` `while` `(low < high) {` ` ` `mid = low + (high - low) / ` `2` `;` ` ` `// If the current term is less than` ` ` `// n then we need to increase low` ` ` `// to mid + 1` ` ` `if` `(divTermCount(a, b, c, mid) < n)` ` ` `low = mid + ` `1` `;` ` ` ` ` `// If current term is greater than equal to` ` ` `// n then high = mid` ` ` `else` ` ` `high = mid;` ` ` `}` ` ` `return` `low;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `a = ` `2` `, b = ` `3` `, c = ` `5` `, n = ` `10` `;` ` ` `System.out.println(findNthTerm(a, b, c, n));` ` ` `}` `}` `// This code is contributed by` `// Rajnis09` |

## Python

`# Python3 implementation of the approach` `# Function to return` `# gcd of a and b` `def` `gcd(a, b):` ` ` `if` `(a ` `=` `=` `0` `):` ` ` `return` `b` ` ` `return` `gcd(b ` `%` `a, a)` `# Function to return the lcm of a and b` `def` `lcm(a, b):` ` ` `return` `((a ` `*` `b) ` `/` `/` `gcd(a, b))` `# Function to return the count of numbers` `# from 1 to num which are divisible by a, b or c` `def` `divTermCount(a, b, c, num):` ` ` `# Calculate number of terms divisible by a and` ` ` `# by b and by c then, remove the terms which is are` ` ` `# divisible by both a and b, both b and c, both` ` ` `# c and a and then add which are divisible by a and` ` ` `# b and c` ` ` `return` `((num ` `/` `/` `a) ` `+` `(num ` `/` `/` `b) ` `+` `(num ` `/` `/` `c)` ` ` `-` `(num ` `/` `/` `lcm(a, b))` ` ` `-` `(num ` `/` `/` `lcm(b, c))` ` ` `-` `(num ` `/` `/` `lcm(a, c))` ` ` `+` `(num ` `/` `/` `lcm(a, lcm(b, c))))` `# Function to find the nth term` `# divisible by a, b or c` `# by using binary search` `def` `findNthTerm(a, b, c, n):` ` ` `# Set low to 1 and high to max (a, b, c) * n` ` ` `low ` `=` `1` ` ` `high ` `=` `10` `*` `*` `9` ` ` `mid` `=` `0` ` ` `while` `(low < high):` ` ` `mid ` `=` `low ` `+` `(high ` `-` `low) ` `/` `/` `2` ` ` `# If the current term is less than` ` ` `# n then we need to increase low` ` ` `# to mid + 1` ` ` `if` `(divTermCount(a, b, c, mid) < n):` ` ` `low ` `=` `mid ` `+` `1` ` ` `# If current term is greater than equal to` ` ` `# n then high = mid` ` ` `else` `:` ` ` `high ` `=` `mid` ` ` `return` `low` `# Driver code` `a ` `=` `2` `b ` `=` `3` `c ` `=` `5` `n ` `=` `10` `print` `(findNthTerm(a, b, c, n))` `# This code is contributed by mohit kumar 29` |

## C#

`// C# implementation of the approach` `using` `System;` ` ` `class` `GFG` `{` ` ` ` ` `// Function to return` ` ` `// gcd of a and b` ` ` `static` `int` `gcd(` `int` `a, ` `int` `b)` ` ` `{` ` ` `if` `(a == 0)` ` ` `return` `b;` ` ` ` ` `return` `gcd(b % a, a);` ` ` `}` ` ` `// Function to return the lcm of a and b` ` ` `static` `int` `lcm(` `int` `a, ` `int` `b)` ` ` `{` ` ` `return` `(a * b) / gcd(a, b);` ` ` `}` ` ` `// Function to return the count of numbers` ` ` `// from 1 to num which are divisible by a, b or c` ` ` `static` `int` `divTermCount(` `int` `a, ` `int` `b, ` `int` `c, ` `int` `num)` ` ` `{` ` ` `// Calculate number of terms divisible by a and` ` ` `// by b and by c then, remove the terms which is are` ` ` `// divisible by both a and b, both b and c, both` ` ` `// c and a and then add which are divisible by a and` ` ` `// b and c` ` ` `return` `((num / a) + (num / b) + (num / c)` ` ` `- (num / lcm(a, b))` ` ` `- (num / lcm(b, c))` ` ` `- (num / lcm(a, c))` ` ` `+ (num / lcm(a, lcm(b, c))));` ` ` `}` ` ` `// Function to find the nth term` ` ` `// divisible by a, b or c` ` ` `// by using binary search` ` ` `static` `int` `findNthTerm(` `int` `a, ` `int` `b, ` `int` `c, ` `int` `n)` ` ` `{` ` ` `// Set low to 1 and high to max (a, b, c) * n` ` ` `int` `low = 1, high = ` `int` `.MaxValue, mid;` ` ` `while` `(low < high) {` ` ` `mid = low + (high - low) / 2;` ` ` `// If the current term is less than` ` ` `// n then we need to increase low` ` ` `// to mid + 1` ` ` `if` `(divTermCount(a, b, c, mid) < n)` ` ` `low = mid + 1;` ` ` ` ` `// If current term is greater than equal to` ` ` `// n then high = mid` ` ` `else` ` ` `high = mid;` ` ` `}` ` ` `return` `low;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `Main(String[] args)` ` ` `{` ` ` `int` `a = 2, b = 3, c = 5, n = 10;` ` ` `Console.WriteLine(findNthTerm(a, b, c, n));` ` ` `}` `}` `/* This code is contributed by PrinciRaj1992 */` |

## Javascript

`<script>` `// Javascript implementation of the approach` `// Function to return` `// gcd of a and b` `function` `gcd(a, b)` `{` ` ` `if` `(a == 0)` ` ` `return` `b;` ` ` `return` `gcd(b % a, a);` `}` `// Function to return the lcm of a and b` `function` `lcm(a, b)` `{` ` ` `return` `parseInt((a * b) / gcd(a, b));` `}` `// Function to return the count of numbers` `// from 1 to num which are divisible by a, b or c` `function` `divTermCount(a, b, c, num)` `{` ` ` `// Calculate number of terms divisible by a and` ` ` `// by b and by c then, remove the terms which is are` ` ` `// divisible by both a and b, both b and c, both` ` ` `// c and a and then add which are divisible by a and` ` ` `// b and c` ` ` `return` `(parseInt(num / a) + parseInt(num / b) +` ` ` `parseInt(num / c)` ` ` `- parseInt(num / lcm(a, b))` ` ` `- parseInt(num / lcm(b, c))` ` ` `- parseInt(num / lcm(a, c))` ` ` `+ parseInt(num / lcm(a, lcm(b, c))));` `}` `// Function to find the nth term` `// divisible by a, b or c` `// by using binary search` `function` `findNthTerm(a, b, c, n)` `{` ` ` `// Set low to 1 and high to max (a, b, c) * n` ` ` `let low = 1, high = Number.MAX_VALUE, mid;` ` ` `while` `(low < high) {` ` ` `mid = low + parseInt((high - low) / 2);` ` ` `// If the current term is less than` ` ` `// n then we need to increase low` ` ` `// to mid + 1` ` ` `if` `(divTermCount(a, b, c, mid) < n)` ` ` `low = mid + 1;` ` ` `// If current term is greater than equal to` ` ` `// n then high = mid` ` ` `else` ` ` `high = mid;` ` ` `}` ` ` `return` `low;` `}` `// Driver code` ` ` `let a = 2, b = 3, c = 5, n = 10;` ` ` `document.write(findNthTerm(a, b, c, n));` `</script>` |

**Output:**

14

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.