[LeetCode] 878. Nth Magical Number

출처: https://leetcode.com/problems/nth-magical-number/

Nth Magical Number - LeetCode

문제

a 또는 b로 나누어지는 양의 정수는 마술적(magical)인 숫자이다.

 

세 정수 n, a 그리고 b가 주어지면, n번째 마술적인 숫자를 반환하라. 답이 매우 클 경우를 대비해서, 1000000007로 나눈 나머지를 반환하라.

예제

Input: n = 1, a = 2, b = 3
Output: 2

Input: n = 5, a = 2, b = 4
Output: 10

Input: n = 3, a = 6, b = 4
Output: 8

풀이

찾아야 하는 Magical한 숫자를 X라고 정의하면, a와 b 그리고 n에 대해서 다음과 같이 정의할 수 있다.

• ⌊X/a⌋ + ⌊X/b⌋ − ⌊X/lcm(a, b)⌋ >= n

 

이 수식의 의미를 살펴보기 위해 a = 2, b = 3인 예를 보자.

a = 2, b = 3

a와 b로 만들 수 있는 Magical한 숫자는 아래와 같다.

2  3  4  6  8  9  10  12, ...

현재 나열된 숫자에서

- a의 배수는 몇 개인가? 6개 (2, 4, 6, 8, 10, 12)
- b의 배수는 몇 개인가? 4개 (3, 6, 9, 12)
- a의 배수이면서 b의 배수인 수는 몇 개인가? 2개 (6, 12)

1) 숫자 12는 a와 b로 만들 수 있는 Magical한 숫자 중 8번째에 해당하는데,
위에서 구한 3개의 질문에 대한 대답으로 찾을 수 있는 값이다.
: 8 = 6 + 4 - 2

2) 숫자 8은 a와 b로 만들 수 있는 Magical한 숫자 중 5번째에 해당하는데,
마찬가지로 (8까지의) a의 배수의 개수 + b의 배수의 개수 - 공통 배수의 개수 로 구할 수 있다.
: 5 = 3 + 2 - 1

즉, 찾고자 하는 n번째 Magical한 숫자를 X라고 할 때, 다음의 수식이 성립한다.
- ⌊X/a⌋ + ⌊X/b⌋ − ⌊X/lcm(a, b)⌋ >= n

그렇다면 이 수식을 만족하는 X를 어떻게 찾을 수 있을까.

 

여러 방법이 있겠지만, 그나마 쉬우면서 효율성을 챙기는 방법으로는 이진탐색 알고리즘을 적용하는 것이라 생각한다.
찾고자 하는 숫자 X의 범위가 0 ~ n*min(a, b)이라는 것을 이용해서 다음과 같이 탐색 알고리즘을 만들 수 있다.

// gcd = 최대 공약수 계산 함수
gcd = (x, y) => {
  if (x == 0) return y;
  return gcd(y % x, x);
}

// lcm = a와 b의 최소공배수
const lcm = (a * b) / gcd(a, b);

let lo = 0, hi = n * Math.min(a, b);
while (lo < hi) {
  const mid = lo + Math.trunc((hi - lo) / 2);

  if (Math.trunc(mid / a) + Math.trunc(mid / b) - Math.trunc(mid / lcm) >= n) {
  	hi = mid;
  } else {
  	lo = mid + 1;
  }
}

 

Github: 878.js

opwe37/Algorithm-Study