Nth Magical Number LeetCode solution in Python

1
# Runtime: 24 ms (Top 100.0%) | Memory: 16.28 MB (Top 81.4%)
2

3

4
class Solution:
5
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
6
        import math
7

8
        lcm = A * B // math.gcd(A, B)
9
        l, r = 2, 10**14
10
        while l <= r:
11
            mid = (l + r) // 2
12
            n = mid // A + mid // B - mid // lcm
13
            if n >= N:
14
                r = mid - 1
15

16
            else:
17
                l = mid + 1
18
        return l % (10**9 + 7)