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 <= 1092 <= 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)
}
Input
n = 1, a = 2, b = 3
Output
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)
Input
n = 1, a = 2, b = 3
Output
2