LeetCode 878 - Nth Magical Number
The problem asks us to find the nth positive integer that is divisible by either a or b. A number is considered magical if at least one of the following is true: - It is divisible by a - It is divisible by b We are given three integers: - n, the position of the magical number…
Difficulty: 🔴 Hard
Topics: Math, Binary Search
Solution
Problem Understanding
The problem asks us to find the nth positive integer that is divisible by either a or b. A number is considered magical if at least one of the following is true:
- It is divisible by
a - It is divisible by
b
We are given three integers:
n, the position of the magical number we wanta, one divisorb, another divisor
The task is to return the nth magical number modulo 10^9 + 7.
For example, if a = 2 and b = 3, the magical numbers are:
2, 3, 4, 6, 8, 9, 10, 12, ...
The 4th magical number is 6.
The key challenge comes from the constraints. The value of n can be as large as 10^9, which immediately tells us that generating magical numbers one by one is impossible. Even a linear scan through integers would be far too slow.
The values of a and b are much smaller, at most 4 * 10^4, but that does not significantly reduce the difficulty because the resulting magical numbers themselves can become extremely large.
An important detail is that numbers divisible by both a and b should only be counted once. This means we need careful handling of overlapping multiples. The least common multiple, or LCM, becomes very important because any number divisible by both a and b must be divisible by lcm(a, b).
Several edge cases are important:
- When
a == b, every magical number is simply a multiple of that value. - When one divisor is a multiple of the other, many numbers overlap.
- When
nis extremely large, intermediate calculations may exceed 32-bit integer limits. - The result itself may be huge, which is why the modulo operation is required.
Approaches
Brute Force Approach
A straightforward approach would be to iterate through positive integers and count how many are divisible by either a or b.
For each number x:
- If
x % a == 0orx % b == 0, increment the magical count. - Once the count reaches
n, returnx.
This works because it explicitly constructs the sequence of magical numbers in sorted order.
However, this approach is far too slow. The nth magical number may be extremely large, especially when n = 10^9. Iterating through billions of integers is not feasible.
Even if we optimized by generating multiples of a and b separately and merging them, the runtime would still be proportional to n, which is too large.
Optimal Approach
The key insight is that instead of generating magical numbers directly, we can binary search for the answer.
Suppose we pick some number x. We can efficiently compute how many magical numbers are less than or equal to x.
The count is:
$\left\lfloor\frac{x}{a}\right\rfloor + \left\lfloor\frac{x}{b}\right\rfloor - \left\lfloor\frac{x}{\mathrm{lcm}(a,b)}\right\rfloor$
This works because:
x // acounts multiples ofax // bcounts multiples ofb- Numbers divisible by both are counted twice, so we subtract them once using inclusion-exclusion
Now we can ask:
"Is there at least n magical numbers up to x?"
If yes, the answer might be smaller.
If no, we need a larger value.
This monotonic property makes binary search possible.
Comparison of Approaches
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(answer) | O(1) | Iterates through numbers one by one and counts magical numbers |
| Optimal | O(log(answer)) | O(1) | Uses binary search with inclusion-exclusion counting |
Algorithm Walkthrough
- Compute the greatest common divisor, or GCD, of
aandb.
The least common multiple is needed to correctly count overlapping multiples. We compute it using:
$\mathrm{lcm}(a,b)=\frac{a\times b}{\gcd(a,b)}$ 2. Define the binary search range.
The smallest possible magical number is min(a, b).
The largest possible answer is n * min(a, b) because even if every magical number were just multiples of the smaller divisor, the nth one could not exceed this value.
3. Perform binary search.
For a midpoint mid, calculate how many magical numbers are less than or equal to mid.
The count formula is:
$\left\lfloor\frac{mid}{a}\right\rfloor + \left\lfloor\frac{mid}{b}\right\rfloor - \left\lfloor\frac{mid}{\mathrm{lcm}(a,b)}\right\rfloor$
4. Compare the count with n.
If the count is at least n, then mid may already be the answer, so move the right boundary leftward.
Otherwise, there are not enough magical numbers yet, so move the left boundary rightward. 5. Continue until the search converges.
Binary search stops when left == right. At this point, we have found the smallest number containing at least n magical numbers, which must be the nth magical number.
6. Return the answer modulo 10^9 + 7.
Why it works
The correctness relies on the monotonic nature of the counting function.
As x increases, the number of magical numbers less than or equal to x never decreases. Therefore, there exists a smallest value x such that the count is at least n.
Binary search efficiently locates this boundary.
The inclusion-exclusion formula guarantees that overlapping multiples are counted exactly once, ensuring the count is accurate.
Python Solution
class Solution:
def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
MOD = 10**9 + 7
def gcd(x: int, y: int) -> int:
while y:
x, y = y, x % y
return x
lcm = (a * b) // gcd(a, b)
left = min(a, b)
right = n * min(a, b)
while left < right:
mid = (left + right) // 2
count = (
mid // a +
mid // b -
mid // lcm
)
if count >= n:
right = mid
else:
left = mid + 1
return left % MOD
The implementation begins by defining a helper function for computing the greatest common divisor. This is used to calculate the least common multiple safely and efficiently.
Next, the binary search range is initialized. The lower bound is the smaller divisor because the first magical number cannot be smaller than that. The upper bound is n * min(a, b).
Inside the binary search loop, the midpoint is evaluated. The code computes how many magical numbers exist up to mid using inclusion-exclusion.
If enough magical numbers exist, the algorithm narrows the search to the left half because we want the smallest valid value. Otherwise, it searches the right half.
Once the search completes, left contains the exact nth magical number. The modulo operation is applied only at the end to preserve correctness during binary search calculations.
Go Solution
func nthMagicalNumber(n int, a int, b int) int {
const MOD int = 1_000_000_007
gcd := func(x int, y int) int {
for y != 0 {
x, y = y, x%y
}
return x
}
lcm := (a * b) / gcd(a, b)
left := min(a, b)
right := n * min(a, b)
for left < right {
mid := left + (right-left)/2
count := mid/a + mid/b - mid/lcm
if count >= n {
right = mid
} else {
left = mid + 1
}
}
return left % MOD
}
func min(x int, y int) int {
if x < y {
return x
}
return y
}
The Go implementation follows the same logic as the Python version, but there are a few language-specific considerations.
Go does not include a built-in min function for integers, so we define one manually.
The binary search midpoint is calculated using:
mid := left + (right-left)/2
This pattern avoids potential overflow in languages with fixed integer sizes.
Go integers are large enough for this problem on modern LeetCode environments, but using careful arithmetic is still good practice.
Worked Examples
Example 1
Input:
n = 1, a = 2, b = 3
First compute:
gcd(2, 3) = 1lcm = 6
Initial search range:
| Variable | Value |
|---|---|
| left | 2 |
| right | 2 |
Since left == right, the binary search immediately ends.
Answer:
2
Example 2
Input:
n = 4, a = 2, b = 3
Magical numbers are:
2, 3, 4, 6, 8, ...
The 4th magical number is 6.
Compute:
gcd(2, 3) = 1lcm = 6
Initial range:
| Variable | Value |
|---|---|
| left | 2 |
| right | 8 |
Iteration 1
| Variable | Value |
|---|---|
| mid | 5 |
Count:
| Expression | Value |
|---|---|
| 5 // 2 | 2 |
| 5 // 3 | 1 |
| 5 // 6 | 0 |
| total | 3 |
Since 3 < 4, move rightward.
| Variable | New Value |
|---|---|
| left | 6 |
Iteration 2
| Variable | Value |
|---|---|
| left | 6 |
| right | 8 |
| mid | 7 |
Count:
| Expression | Value |
|---|---|
| 7 // 2 | 3 |
| 7 // 3 | 2 |
| 7 // 6 | 1 |
| total | 4 |
Since 4 >= 4, move leftward.
| Variable | New Value |
|---|---|
| right | 7 |
Iteration 3
| Variable | Value |
|---|---|
| left | 6 |
| right | 7 |
| mid | 6 |
Count:
| Expression | Value |
|---|---|
| 6 // 2 | 3 |
| 6 // 3 | 2 |
| 6 // 6 | 1 |
| total | 4 |
Again, 4 >= 4, so:
| Variable | New Value |
|---|---|
| right | 6 |
Now left == right == 6.
Final answer:
6
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(log(n * min(a, b))) | Binary search over the answer range |
| Space | O(1) | Only a few integer variables are used |
The binary search range extends up to approximately n * min(a, b). Each iteration halves the search space, so the number of iterations is logarithmic.
Inside each iteration, only constant-time arithmetic operations are performed. Therefore, the overall runtime is logarithmic.
The algorithm uses no auxiliary data structures, so the space complexity is constant.
Test Cases
sol = Solution()
# Provided examples
assert sol.nthMagicalNumber(1, 2, 3) == 2 # first magical number
assert sol.nthMagicalNumber(4, 2, 3) == 6 # overlapping multiple
# Equal divisors
assert sol.nthMagicalNumber(5, 4, 4) == 20 # all multiples of 4
# One divisor is multiple of the other
assert sol.nthMagicalNumber(5, 2, 4) == 10 # duplicates handled correctly
# Small inputs
assert sol.nthMagicalNumber(3, 6, 8) == 16 # sequence: 6,8,12,16
# Large n
assert sol.nthMagicalNumber(1000000000, 40000, 40000) == 999720007 # stress test
# Co-prime divisors
assert sol.nthMagicalNumber(10, 7, 13) == 49 # mixed sequence
# Large overlap frequency
assert sol.nthMagicalNumber(8, 3, 6) == 24 # every multiple of 6 overlaps
# Minimal n
assert sol.nthMagicalNumber(1, 39999, 40000) == 39999 # smallest magical number
print("All tests passed.")
Test Summary
| Test | Why |
|---|---|
n=1, a=2, b=3 |
Validates smallest possible n |
n=4, a=2, b=3 |
Verifies inclusion-exclusion counting |
a == b |
Ensures duplicate divisors work correctly |
a=2, b=4 |
Tests overlapping multiples |
| Small mixed divisors | Confirms general correctness |
Very large n |
Stress tests binary search efficiency |
| Co-prime divisors | Tests sparse overlap |
| Frequent overlap | Ensures LCM subtraction is correct |
| Large divisor values | Tests upper constraint handling |
Edge Cases
One important edge case occurs when a == b. In this situation, every magical number is simply a multiple of that single value. A buggy implementation might double count every number because it adds both mid // a and mid // b. The inclusion-exclusion subtraction using the LCM fixes this automatically because the LCM equals the divisor itself.
Another tricky case happens when one divisor is a multiple of the other, such as a = 2 and b = 4. Many numbers belong to both sets of multiples. Without subtracting multiples of the LCM, the count would be inflated and binary search would converge to the wrong answer. The formula ensures every magical number is counted exactly once.
Large values of n create another potential issue. The answer may exceed 32-bit integer limits. For example, n = 10^9 and a = 40000 produce values around 4 * 10^13. Languages with fixed-width integers can overflow if calculations are not handled carefully. The implementation avoids this by using integer types large enough to store intermediate values safely.
A final edge case involves the modulo operation. Applying modulo during binary search would corrupt the ordering relationship required for correctness. The implementation only applies modulo after the exact answer has been found, preserving the integrity of the search process.