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
            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()

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.