What is the primary pattern used to solve the Nth Magical Number problem?

The primary pattern used is binary search over the valid answer space, combined with counting magical numbers through inclusion-exclusion.

How can I avoid overflow when dealing with large numbers in this problem?

You should apply modulo 10^9 + 7 throughout your calculations to prevent overflow and return a manageable result.

What is the time complexity of the binary search solution for the Nth Magical Number problem?

The time complexity is O(log(max(n, a*b))) due to the binary search over the range of possible magical numbers.

Can this problem be solved without binary search?

While binary search is the most efficient method, solving this problem with a brute force approach is not feasible for large inputs due to time constraints.

What is the inclusion-exclusion principle in the context of this problem?

Inclusion-exclusion helps count how many numbers are divisible by a or b by adding the multiples of a and b, and subtracting the multiples of both a and b to avoid double-counting.

#878

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

第 N 个神奇数字

一个正整数如果能被 a 或 b 整除，那么它是神奇的。给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案对 10 9 + 7 取模后的值。示例 1：输入： n = 1, a = 2, b = 3 输出： 2 示例 2：输入： n = 4, a =…

数学二分查找

题目描述

一个正整数如果能被 a 或 b 整除，那么它是神奇的。

给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案对 10⁹ + 7 取模后的值。

示例 1：

输入：n = 1, a = 2, b = 3
输出：2

示例 2：

输入：n = 4, a = 2, b = 3
输出：6

提示：

1 <= n <= 10⁹
2 <= a, b <= 4 * 10⁴

lightbulb

解题思路

方法一：数学 + 二分查找

根据题目描述，神奇数字是能被 $a$ 或 $b$ 整除的正整数。

而我们知道，对于任意正整数 $x$ ，在 $[1,..x]$ 范围内，能被 $a$ 整除的数有 $\lfloor \frac{x}{a} \rfloor$ 个，能被 $b$ 整除的数有 $\lfloor \frac{x}{b} \rfloor$ 个，能被 $a$ 和 $b$ 同时整除的数有 $\lfloor \frac{x}{c} \rfloor$ 个，其中 $c$ 是 $a$ 和 $b$ 的最小公倍数。最小公倍数的计算公式为 $c = lcm(a, b) = \frac{a \times b}{gcd(a, b)}$ 。

因此，对于任意正整数 $x$ ，在 $[1,..x]$ 范围内，神奇数字的个数为：

\lfloor \frac{x}{a} \rfloor + \lfloor \frac{x}{b} \rfloor - \lfloor \frac{x}{c} \rfloor

为什么要减去 $\lfloor \frac{x}{c} \rfloor$ 呢？可以这样理解，在 $[1,..x]$ 范围内，能被 $a$ 和 $b$ 同时整除的数，它们既能被 $a$ 整除，也能被 $b$ 整除，因此它们被计算了两次，需要减去一次。

题目要我们找到第 $n$ 个神奇数字，也即是说，要找到一个最小的正整数 $x$ ，使得以下式子成立：

\lfloor \frac{x}{a} \rfloor + \lfloor \frac{x}{b} \rfloor - \lfloor \frac{x}{c} \rfloor \geq n

随着 $x$ 的增大，神奇数字的个数也会增大，因此我们可以使用二分查找的方法，找到最小的正整数 $x$ ，使得上述式子成立。

注意答案的取模操作。

时间复杂度 $O(\log M)$ ，空间复杂度 $O(1)$ 。其中 $M$ 是二分查找的上界，本题可以取 $M=(a+b) \times n$ 。

1

2

3

4

5

6

7

class Solution:
    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
        mod = 10**9 + 7
        c = lcm(a, b)
        r = (a + b) * n
        return bisect_left(range(r), x=n, key=lambda x: x // a + x // b - x // c) % mod

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates understanding of binary search and inclusion-exclusion principles.
question_mark
The candidate can efficiently handle large inputs and avoid brute force solutions.
question_mark
The candidate successfully uses modulo arithmetic to prevent overflow in large numbers.

warning

常见陷阱

外企场景

error
Forgetting to handle large values with modulo operation, causing overflow.
error
Misapplying the inclusion-exclusion principle when counting multiples of a and b.
error
Using a brute force solution that will not scale well with the input size.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if n is extremely large, and we need to handle the computation efficiently?
arrow_right_alt
What if a and b are very large numbers? How does this affect the binary search range?
arrow_right_alt
Can this problem be solved with a greedy approach instead of binary search?

help

常见问题

外企场景

继续练习

#887 鸡蛋掉落 #902 最大为 N 的数字组合 #793 阶乘函数后 K 个零