# 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:

1. is there a way to go from X → n?
2. 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

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

• Time: `O()`
• Space: `O()`
##### Tanishq Chaudhary Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### 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

This site uses Akismet to reduce spam. Learn how your comment data is processed.