[LC] 1201. Ugly Number III

[seungriyou]

<1201. Ugly Number III> (#98)

Approach

• condition 함수인 ugly(num)을 num 이하인 ugly number의 개수가 n개 이하인지 여부를 반환하도록 설계한다.

  num 이하인 ugly number의 개수는 집합 관계와 LCM(최소공배수)를 사용하여 다음과 같이 계산할 수 있다.

  num // a + num // b + num // c 
  - (num // lcm(a, b) + num // lcm(b, c) + num // lcm(c, a)) 
  + num // lcm(a, b, c)

  이렇게 하면 ugly(num)을 만족하는 가장 작은 num(➡️ n-th 원소)을 구하면 된다.

  # lcm 구하기
  ab, bc, ca = a * b // gcd(a, b), b * c // gcd(b, c), c * a // gcd(c, a)
  abc = a * bc // gcd(a, bc)
  
  def ugly(num):
    return (
        num // a + num // b + num // c
        - (num // ab + num // bc + num // ca)
        + num // abc
    ) >= n

• 문제에서 search range가 [1, 2 * 10^9]로 주어졌으므로, 조건을 만족하는 값 중 가장 작은 값을 찾기 위해 다음과 같이 left를 더 찾는 로직을 작성할 수 있다.

  lo, hi = 1, 2 * 10 ** 9
  
  while lo < hi:
    mid = lo + (hi - lo) // 2
    if ugly(mid):
        hi = mid    # look for left
    else:
        lo = mid + 1
  
  return lo

Complexity

• Time: O(logn)
• Space: O(1)