## Algorithm

Problem Name: 878. Nth Magical Number

A positive integer is magical if it is divisible by either `a` or `b`.

Given the three integers `n`, `a`, and `b`, return the `nth` magical number. Since the answer may be very large, return it modulo `109 + 7`.

Example 1:

```Input: n = 1, a = 2, b = 3
Output: 2
```

Example 2:

```Input: n = 4, a = 2, b = 3
Output: 6
```

Constraints:

• `1 <= n <= 109`
• `2 <= a, b <= 4 * 104`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const gcd = (x, y) => {
while (y > 0) [x, y] = [y, x % y]
return x
}
const lcm = (x, y) => (x * y) / gcd(x, y)
const nthMagicalNumber = function(N, A, B) {
let l = lcm(A, B)
const seq = {}
for (let i = 1; i  <  Math.floor(l / A) + 1; i++) seq[i * A] = 1
for (let i = 1; i  <  Math.floor(l / B) + 1; i++) seq[i * B] = 1
const arr = Object.keys(seq)
.sort((a, b) => a - b)
.map(el => +el)
let idx = N % arr.length === 0 ? arr.length - 1 : (N % arr.length) - 1
let res = Math.floor((N - 1) / arr.length) * arr[arr.length - 1] + arr[idx]
return res % (1e9 + 7)
}
``````
Copy The Code &

Input

cmd
n = 1, a = 2, b = 3

Output

cmd
2

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:

def gcd(self, a, b):
while b:
a, b = b, a % b
return a

def count(self, num, A, B, C):
return num // A + num // B - num // C

def nthMagicalNumber(self, N, A, B):
l, r, C = 2, 2 ** 63  - 1, A * B // self.gcd(A, B)
while l < r:
mid = (l + r) // 2
if self.count(mid, A, B, C) < N:
l = mid + 1
else:
r = mid
return l % (10 ** 9 + 7)
``````
Copy The Code &

Input

cmd
n = 1, a = 2, b = 3

Output

cmd
2