878. Nth Magical Number

Python

Consier the target magical number is X, then

$$n = X/a + X/b - X/LCM(a,b)$$

1. Deside the upbound and lowbound of the possible answer
2. Doing binary search of target X inside the range

import math


class Solution:
    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        small = min(a, b)
        large = max(a, b)
        lcm = math.lcm(a, b)

        lowbound = small
        upbound = large * n

        # Binary Search between low~up
        while lowbound < upbound:
            mid = (lowbound+upbound) // 2
            if mid // small + mid // large - mid // lcm < n:
                lowbound = mid + 1
            else:
                upbound = mid

        return lowbound % (10**9 + 7)