#878

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Nth Magical Number

Find the nth magical number divisible by a or b, using binary search to efficiently handle large inputs.

Problem Statement

A number is magical if it is divisible by either a or b. Given integers n, a, and b, you need to return the nth magical number, modulo 10^9 + 7. The value of n can be as large as 10^9, so an efficient approach is necessary.

To find the nth magical number, one must calculate the count of magical numbers up to a certain value and use binary search to narrow down the valid range. The answer should be returned modulo 10^9 + 7 due to potentially large results.

Examples

Example 1

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

Output: 2

Example details omitted.

Example 2

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

Output: 6

Example details omitted.

Constraints

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

Solution Approach

Binary Search Approach

We can use binary search over the range of possible magical numbers. The main idea is to check how many magical numbers exist below a certain value by counting those divisible by a and b. The binary search helps efficiently hone in on the nth magical number.

Counting Magical Numbers

For a given value, we calculate how many numbers are divisible by a or b using the inclusion-exclusion principle. The number of magical numbers below a value x can be determined by counting multiples of a, multiples of b, and subtracting the overlap (multiples of both a and b).

Modulo Operation

Since the result could be very large, we return the nth magical number modulo 10^9 + 7. This ensures that we stay within manageable number sizes while avoiding overflow.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(log(max(n, a*b))) due to the binary search over the possible range. The space complexity is O(1) as we only use a few variables to perform the binary search and counting operations.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

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

Continue Practicing

#887 super egg drop #902 numbers at most n given digit set #793 preimage size of factorial zeroes function