Write a program to find the n-th ugly number.
Ugly numbers are positive integers which are divisible by a or b or c.
 
Example 1:
Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.
Example 2:
Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.

Example 3:
Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.

Example 4:
Input: n = 1000000000, a = 2, b = 217983653, c = 336916467
Output: 1999999984

 
Constraints:

1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
It's guaranteed that the result will be in range [1, 2 * 10^9]

Difficulty: interview

Starter code:

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        

Solutions:
class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        
        def enough(num):
            total = num//a + num//b + num//c -num//ab - num//bc - num//ac + num//abc
            return total>=n
    
    
        ab = (a*b)//math.gcd(a,b)
        ac = (a*c)//math.gcd(a,c)
        bc = (b*c)//math.gcd(b,c)
        abc = (a*bc)//math.gcd(a,bc)
        
        
        left , right = 1, min(a,b,c)*n
        
        while left < right:
            mid = left+ (right-left)//2
            if enough(mid): right = mid
            else : left = mid + 1
                
        return left

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:     
        ab = a*b//math.gcd(a,b)
        bc = b*c//math.gcd(b,c)
        ca = a*c//math.gcd(c,a)
        abc = ab*c//math.gcd(ab,c)
        lo = 1
        hi = 2*10**9
        while lo < hi:
            m = (lo+hi) //2
            cnt = m//a + m//b + m//c - m//ab - m//bc - m//ca + m//abc
            if cnt < n:
                lo = m+1
            else:
                hi = m
        return lo

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        def enough(num) -> bool:
            total = mid//a + mid//b + mid//c - mid//ab - mid//ac - mid//bc + mid//abc
            return total >= n

        ab = a * b // math.gcd(a, b)
        ac = a * c // math.gcd(a, c)
        bc = b * c // math.gcd(b, c)
        abc = a * bc // math.gcd(a, bc)
        left, right = 1, 10 ** 10
        while left < right:
            mid = left + (right - left) // 2
            if enough(mid):
                right = mid
            else:
                left = mid + 1
        return left    

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        def lcm(a, b):
            return a * b // math.gcd(a, b)
        
        nums = sorted([a, b, c])
        nums2 = [lcm(a, b), lcm(b, c), lcm(a, c)]
        nums3 = lcm(nums2[0], c)
        
        lo, hi = n, nums[-1] * n
        
        while lo < hi:
            mid = (lo + hi) // 2
            rank = (sum(mid // n for n in nums) - sum(mid//n for n in nums2) + mid // nums3)
            if rank < n:
                lo = mid + 1
            else:
                hi = mid
        return lo



class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        '''
        the fact: num1*num2=LCM*GCD -> LCM=num1*num2//gcd
        
        '''
        ab = a*b//math.gcd(a, b)
        bc = b*c//math.gcd(c, b)
        ac = a*c//math.gcd(a, c)
        abc = ab*c//math.gcd(ab, c)
        
        
        def nthUgly(k:int) -> bool: #are there more than n uglies below it number?
        
            h = k//a + k//b + k//c - k//ab - k//ac - k//bc+ k//abc
            
            if h >= n:
                return True
            return False
        
        left, right = 1, 10**10
        #print(nthUgly(10))
        while left < right:
            mid =(right + left)//2
            if nthUgly(mid):
                right = mid
            else:
                left = mid + 1
            
        return left



class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        '''
        the fact: num1*num2=LCM*GCD -> LCM=num1*num2//gcd
        
        '''
        ab=a*b//math.gcd(a,b)
        ac=a*c//math.gcd(a,c)
        bc=b*c//math.gcd(b,c)
        abc=ab*c//math.gcd(ab,c)
        
        def has_nsmaller(num):
            k=num//a+num//b+num//c-num//ac-num//ab-num//bc+num//abc
            return k>=n
        
        low,high=0,2*10**9
        while low<high:
            mid=(low+high)//2
            if has_nsmaller(mid):
                high=mid
            else:
                low=mid+1
        return low


import math
class Solution:
    def ugly(self, n, a, b, c, ab, ac, bc, abc, num):
        return ((num // a) + (num // b) + (num // c) - (num // ab) - (num // ac) - (num // bc) + (num // abc)) >= n
        
        
        
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        left = min(a,b,c)
        right = a * b * c * n
        
        ab = (a*b) // math.gcd(a,b)
        ac = (a*c) // math.gcd(a,c)
        bc = (b*c) // math.gcd(b,c)
        
        abc = (a * bc) // math.gcd(a,bc)
        
        while left < right:
            mid = left + (right - left) // 2
            if self.ugly(n, a, b, c, ab, ac, bc, abc, mid):
                right = mid
            else:
                left = mid + 1
                
        return left

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        def gcd(a, b):
            while b:
                a, b = b, a%b
            return a
        
        def lcm(a, b):
            return a*b//gcd(a, b)
        
        def count_ugly(N, a, b, c):
            ab, ac, bc = lcm(a, b), lcm(a, c), lcm(b, c)
            abc = lcm(ab, c)
            return N//a+N//b+N//c-N//ab-N//ac-N//bc+N//abc
            
        s, e =1, 2*10**9
        while s<=e:
            m = s+(e-s)//2
            cnt = count_ugly(m, a, b, c)
            if cnt>=n:
                e = m-1
            else:
                s = m+1
                
        return s
        


class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        ab = a*b//gcd(a, b)
        bc = b*c//gcd(b, c)
        ca = c*a//gcd(c, a)
        abc = ab*c//gcd(ab, c)
        
        def fn(k):
            return k//a + k//b + k//c - k//ab - k//bc - k//ca + k//abc

        lo, hi = 0, 2_000_000_000
        while lo < hi:
            mid = (lo + hi)//2
            if fn(mid) >= n: hi = mid
            else: lo = mid + 1
        return lo

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:        
        lo = 1
        hi = 2*10**9;
        
        ab = a * b // math.gcd(a, b);
        bc = b * c // math.gcd(b, c);
        ac = a * c // math.gcd(a, c);
        abc = a * bc // math.gcd(a, bc);
        
        while lo < hi:
            mid = lo + (hi - lo)//2;
            cnt = mid//a + mid//b + mid//c - mid//ab - mid//bc - mid//ac + mid//abc;
            if cnt < n: 
                lo = mid + 1;
            else:
                hi = mid;
        
        return lo

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        
        def isEnough(num):
            total = num//a + num//b + num//c - num//ab - num//ac - num//bc + num//abc
            return total >= n
        
        ab = a*b // math.gcd(a,b)
        ac = a*c // math.gcd(a,c)
        bc = b*c // math.gcd(b,c)
        abc = a*bc // math.gcd(a,bc)
        
        left = 1
        right = 10 ** 10
        while left < right:
            mid = left + (right - left) // 2
            if isEnough(mid):
                right = mid
            else:
                left = mid + 1
        return left