leetcode 878) Nth Magical Number

LV. Hard 🥵

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

Nth Magical Number - LeetCode

 

문제

A positive integer is magical if it is divisible by either a or b.

Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= n <= 109
• 2 <= a, b <= 4 * 104

문제 해결법

밑에 코드를 2가지 넣어뒀다.

1번째는 타임아웃 난 코드이고, 2번째가 정답 코드이다

처음에는 그냥 0부터 magical number까지 다 돌며 정답을 찾았다 -> n = 1e10, a = 40000, b = 40000에서 타임아웃!!

 

이진 검색을 활용하여 타임아웃 해결!

left = 0, right = max(n * a * b)

n = x(magical number) / a + x / b - x / lcm 이다.

 

이해가 안 되면 밑 박스 안의 예제를 살펴보자.

input : n = 1, a = 2, b = 3

x(magical number) = 2
2 / 2 + 2 / 3 - 2 / 6 = 1 + 0 - 0 = 1 = n

left와 right의 중간값인 mid를 식에 대입하여 mid의 index를 구한다.

만약 mid의 index > n이면 mid ~ right 범위의 수에는 정답이 없으므로 right = mid로 범위 변경을 해준다

마찬가지로 mid의 index < n이면 left ~ mid 범위의 수에는 정답이 없으므로 left = mid로 범위 변경을 해준다

 

mid의 index = n이면 어떻게 해야 될까? 아래 예시를 보자.

input : n = 3, a = 3, b = 5

x(magical number) = 6(3, 5, 6)
x = 6 : 6 / 3 + 6 / 5 - 6 / 15 = 2 + 1 - 0 = 3
x = 7 : 7 / 3 + 7 / 5 - 7 / 15 = 2 + 1 - 0 = 3
x = 8 : 8 / 3 + 8 / 5 - 8 / 15 = 2 + 1 - 0 = 3

분명 magical number은 6인데, 7과 8도 해당식에서 index가 n과 동일하게 나온다

나누기를 해서 몫을 구할 때 나머지를 신경 써주지 않기 때문에 이러한 결과가 나온 것이다

위에 예제를 통해서 x(magical number)은 mid ~ right가 아니라, left ~ mid에 있다는 것을 알 수 있다

 

mid의 index = n이면 x의 값은 left ~ mid 사이에 있을 것이기에 right =mid로 범위 변경을 해준다

 

위와 같은 방식으로 계속 범위를 줄여나가게 되면 left = x - 1, right = x가 된다.

 

해결 코드

• 타임 아웃 난 코드

class Solution {
public:
	int nthMagicalNumber(int n, int a, int b) {
		const int modulo = 1e9 + 7;
		int idx = 0;
		unsigned long long ans;
		unsigned long long temp = 1;

		while (idx != n) {
			if (temp % a == 0 || temp % b == 0) {
				idx++;
				ans = temp;
			}
			temp++;
		}
		return ans % modulo;
	}
};

• 정답 코드

#include <iostream>

/*
** 1 <= n <= 10^9
** 2 <= a, b <= 4 * 10^4
** 나올 수 있는 답의 최대 = 10^9 * 4 * 10^4 = 4 * 10^13 (unsigned longlong)
*/

class Solution {
public:
	int nthMagicalNumber(int n, int a, int b) {
		const int modulo = 1e9 + 7;
		unsigned long long lcm = this->lcm(a, b);
		unsigned long long left = 0;
		//right는 max 값
		unsigned long long right = a * b * n;
		while (left + 1 != right) {
			unsigned long long mid = (left + right) / 2;
			unsigned long long idx = mid / a + mid / b - mid / lcm;
			if (idx >= n)
				right = mid;
			else
				left = mid;
		}
		return right % modulo;
	}
private:
	// 최대공약수
	int gmd(int a, int b) {
		return a == 0 ? b : gmd(b % a, a);
	}
	//최소공배수
	long lcm(int a, int b) {
		return a * b / gmd(a, b);
	}
};

int main() {
	Solution sol;

	// std::cout << sol.nthMagicalNumber(1, 2, 3) << std::endl;
	// std::cout << sol.nthMagicalNumber(4, 2, 3) << std::endl;
	std::cout << sol.nthMagicalNumber(1000000000, 40000, 40000) << std::endl;
}