Problem statement

https://leetcode.com/problems/ugly-number-iii/

Solution

Use binary search and inclusion-exclusion formula to get the answer.

Complexity

Time complexity is ``O(log(n*min(a,b,c)), space complexity is O(1)`.

Code

class Solution:
    def nthUglyNumber(self, n, a, b, c):
        ab, bc, ac = lcm(a, b), lcm(b, c), lcm(a, c)
        abc = lcm(ab, c)
        beg, end = 0, n*min(a, b, c)

        while beg + 1 < end:
            mid = (beg + end)//2
            total = mid//a + mid//b + mid//c - mid//ab - mid//ac - mid//bc + mid//abc
            if total < n:
                beg = mid
            else:
                end = mid
                
        return end