Python 0878.py
class Solution:
def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
# reminds me of FizzBuzz
# compute n for x
def count(x):
# actually the result can be wrong:
# I don't check whether x is magical
one = x // a
two = x // b
both = x // lcm(a, b) # it's possible that a and b share some factors
return one + two - both
left = 0
right = a * n # rough estimate
while left < right:
mid = (left + right) // 2
if count(mid) < n:
left = mid + 1
else:
right = mid
return left % 1_000_000_007
Difficulty
and has an acceptance rate of about 37% (100k+ submissions).
Typical patterns to solve this problem:
- Binary Search
- Math
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation computes the n-th magical number-an integer that is divisible by either of the two given divisors a or b. It does so by combining a counting helper with a binary-search loop that narrows the search interval until the exact value is found. The final result is reduced modulo 1 000 000 007 as required by the problem statement.
Counting magical numbers up to a bound
A nested function named count determines how many magical numbers are less than or equal to a candidate value x. The function uses integer division to count multiples of each divisor and then subtracts the overlap counted twice.
def count(x):
one = x // a
two = x // b
both = x // lcm(a, b)
return one + two - both
The subtraction of both eliminates the double-counted numbers that are multiples of the least common multiple of a and b. By employing the lcm function, the code correctly handles the situation where a and b share common factors, ensuring that the overlap is computed precisely.
Initial search interval
Before the binary search begins, the algorithm establishes a lower bound of 0 and an upper bound based on a simple over-estimate: the product of a and n. This choice guarantees that the n-th magical number lies within the interval, even when a is the smaller divisor.
left = 0
right = a * n
Binary-search loop
The core of the algorithm is a classic binary-search loop that repeatedly halves the interval. At each iteration, the midpoint mid is evaluated with the count helper. If fewer than n magical numbers exist up to mid, the lower bound moves just beyond mid; otherwise, the upper bound contracts to mid. The loop terminates when left meets right, at which point left holds the smallest value whose count is at least n.
while left < right:
mid = (left + right) // 2
if count(mid) < n:
left = mid + 1
else:
right = mid
Because the interval is reduced by roughly half each iteration, the loop converges quickly even for very large inputs.
Final modulo operation
After the binary search finishes, the algorithm returns the found magical number reduced modulo 1 000 000 007. Performing the modulo only once, after the search, avoids unnecessary arithmetic inside the loop and keeps the inner computation fast.
return left % 1_000_000_007
Edge-case handling
The code gracefully deals with inputs where a and b are not coprime. By using the least common multiple in the overlap calculation, it correctly counts numbers that are multiples of both divisors, preventing an inflated count. The initial upper bound a * n also covers the case where a is larger than b, ensuring that the search space always contains the target value regardless of the relative sizes of the divisors.
When n is very large, the binary-search approach still operates efficiently because the number of iterations depends logarithmically on the size of the interval rather than linearly on n. The use of integer division (//) guarantees that the counting operation remains exact and fast for all integer inputs.
Performance optimizations
The algorithm’s primary optimization is the binary-search strategy, which reduces the problem of locating the n-th magical number to a logarithmic number of checks. Each check consists of a few integer divisions and a subtraction, all of which are O(1) operations on typical hardware. By calculating the least common multiple once per count call, the code avoids repeated factorization or gcd calculations inside the loop.
Additionally, the modulo operation is deferred until after the search completes, preventing repeated large-integer modulo calculations that could degrade performance. The choice of right = a * n as the initial bound provides a tight enough interval to keep the number of binary-search steps modest while still guaranteeing correctness.
ELI5 - Simplified Explanation
Imagine there is a magical garden where some flowers only bloom on certain days. Some flowers bloom every time the number of days is a multiple of a first number, and others bloom when the number of days is a multiple of a second number. The goal is to find the specific day when a certain amount of these magical flowers have finished blooming.
To find the right day, the code starts by picking a range that might contain the answer. It looks at the middle of this range and asks how many magical flowers would have bloomed by that time. If the number of flowers is too small, it knows the day must be later, so it throws away the first half of the range. If there are enough flowers, it focuses on the earlier half to see if it can find an even sooner day. By repeating this process over and over, the range gets smaller and smaller until it finds the exact day needed. Because the final result might be a very large number, it uses a special trick to keep the number manageable by dividing it by a large round value and keeping the remainder.
Code Quality
Complexity Analysis
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||
| www | AlgoMonster | C++ | Java | Python | TS | ||||
| WalkCCC | C++ | Java | Python | ||||||
| leetcode.ca | C++ | Java | Go | Python | |||||
| LeetcodeHelp | C++ | Java | Python | ||||||
| Progiez | C++ | Java | Python | ||||||
| github | black-shadows | C++ | |||||||
| charles-wangkai | Java | ||||||||
| everthis | JS | ||||||||
| fpdjsns | C++ | ||||||||
| gouthampradhan | Java | ||||||||
| halfrost | Go | ||||||||
| JoshCrozier | JS | ||||||||
| ruoru | Rust | ||||||||
| suxrobGM | C# | ||||||||
| wisdompeak | C++ | ||||||||
| zfang399 | C++ | ||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||
| WalkCCC | C++, Python, Java | ||||||||
| leetcode.ca | C++, Go, Java, Python | ||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||
| Progiez | C++, Java, Python | ||||||||
| black-shadows | C++, C++ | ||||||||
| charles-wangkai | Java | ||||||||
| everthis | JavaScript | ||||||||
| fpdjsns | C++ | ||||||||
| gouthampradhan | Java | ||||||||
| halfrost | Go | ||||||||
| JoshCrozier | JavaScript | ||||||||
| ruoru | Rust | ||||||||
| suxrobGM | C# | ||||||||
| wisdompeak | C++ | ||||||||
| zfang399 | C++ |
Videos
Solved On The Same Day
- problem 1005: Maximize Sum Of Array After K Negations
- problem 935: Knight Dialer
- problem 1029: Two City Scheduling
- problem 1769: Minimum Number of Operations to Move All Balls to Each Box
- problem 2080: Range Frequency Queries
- problem 793: Preimage Size of Factorial Zeroes Function
- problem 902: Numbers At Most N Given Digit Set
- problem 1751: Maximum Number of Events That Can Be Attended II
- problem 1793: Maximum Score of a Good Subarray
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality