Problem Link

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        left = 1
        right = 2 * 10**9
        while left < right:
            m = left + (right - left) // 2
            cnt = self.count(a, b, c, m)
            if cnt < n:
                left = m + 1
            else:
                right = m
        return left

    """
     count the numebr of positive integers that 
     are divisible by a, b, or c
    """
    def count(self, a, b, c, n):
        return n // a + n // b + n // c - /
               n // self.lcm(a, b) - n // self.lcm(b, c) - n // self.lcm(a, c) + /
               n // self.lcm(a, self.lcm(b, c))

    def gcd(self, a, b) -> int:
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        return self.gcd(b, a % b)

    def lcm(self, a, b) -> int:
        return a * b // self.gcd(a, b)