# 1201. Ugly Number III
#### Difficulty: Medium
link: https://leetcode.com/problems/ugly-number-iii/

### 1. Binary Search
#### $O(log\ (min(a, b, c) * n))$ runtime, $O(1)$ space

題目敘述説要找第kth個xxx，可以轉變思路，每次猜一個數字，檢查這個數字前面是不是有n個ugly number，找到滿足條件的最小值就是第kth個ugly number。

比較快的猜數字算法就是binary search，同樣套用模板。

計算前面有幾個ugly number是本題最需要靈感的地方，直接除a, b, c累加在一起就行，然而最大公倍數會重複計算，所以需要扣掉或補回來。

最大公倍數使用math套件的lcm。

邊界最大值設為min(a, b, c)的n倍，保證至少有n個ugly number；邊界最小值從以下兩者選擇較大的數，min(a, b, c)是第一個ugly number，而第n個ugly number一定比n大。

##### python

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

###### tags: `leetcode`