Nth Magical Number | LeetCode | Solution Explained
LeetCode 878. Nth Magical Number. I explain the binary search solution in detail, along with intuitions and observations and explanations. Problem Link.
0. Nth Magical Number: Problem Discussion
0.0. IO Format
- Given: n, a, b
- Goal: return the nth number which is divisible by a or b
- Constraints:
- 1 <= n <= 10⁹
- 2 <= a, b <= 4 * 10⁴
0.1. Examples
Let’s take the case of a = 2, b = 3. They generate a sequence of 2, 3, 4, 6, 8, 9, 10, and so on.
If we want to know the answer for n = 1, we will look at the first element of the list generated, which is 2. If we want to know for n = 6, we will look at the 6th position (NOTE: these are 1-indexed).

1. Nth Magical Number: Observations & Logic
1.0. Intuitions
- I first thought about priority queue, and maybe I could insert multiples of a, b into the queue in sorted order, and get the nth element easily.
- However, as I started to code it up, I realized its not going well XD
- Then, I looked over at the constraint, n = 10⁹ at max! No way a PQ will work
- But, 10⁹ … is commonly used in binary search questions
- Now the question is, how do we use our direction of binary search?
In a previous solution, Kth Smallest Number in Multiplication Table | LeetCode | Solution Explained, I explained how its a very good idea, to flip the problem on its own head, and see what happens.
In this case, we are going from n –> X, where X is the nth number in the sequence. What if we could go in the reverse direction?

There are two questions now:
- is there a way to go from X → n?
- what do we do of it?
1.1. Solving Problem 1
- We have a sequence of multiples of either a or b → goal: find position
- What are number of multiples of a?
- What are number of multiples of b?
- 2: 2, 4, 6, 8, 10, 12, …
- 3: 6, 9, 12, …
- … There’s overlap!
- LCM(2, 3) gets repeated
- position =
X // a + X // b - X // (LCM(a, b))
- first problem solved!
1.2. Solving Problem 2
- What do we do now?
- Here’s what we know
- we have to use binary search, because n is too large
- 1 <= n <= 10⁹
- 2 <= a, b <= 4 * 10⁴
- given a random number, X, we can return the position
- run a binary search over [1, 10¹⁸]
Wait what? Let’s take an example, a = 2 and b = 3 and n = 4 and see what happens.
For the sake of explaining, I have already set high (h) to be 20, instead of 10¹⁸.

2. Nth Magical Number: Optimized Implementation
2.0. Code
class Solution: def nthMagicalNumber(self, n: int, a: int, b: int) -> int: def lcm(a, b): return a * b // gcd(a, b) def get_total(X, a, b): p, q, r = X//a, X//b, X//lcm(a, b) total = p + q - r return total l, h = 1, 10**18+1 ans = None MOD = 10**9 + 7 while l < h: m = (l + h) // 2 total = get_total(m, a, b) if total < n: l = m + 1 else: h = m return l % MOD
2.1. Complexity Analysis
to be added soon.
- Time:
O()
- Space:
O()
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Reverse integer | InterviewBit | LeetCode | Solution Explained
January 24, 2022
Furthest Building You Can Reach | LeetCode | Solution Explained
January 20, 2022