# 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
**n**th 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

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022

##### Furthest Building You Can Reach | LeetCode | Solution Explained

January 20, 2022

##### Jump Game IV | LeetCode | Solution Explained

January 15, 2022