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

Nth Magical Number: sample test case
Nth Magical Number: sample test case

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?

 Nth Magical Number: reversing the problem
Nth Magical Number: reversing the problem

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¹⁸.

 Nth Magical Number: a dry run of a small test case
Nth Magical Number: a dry run of a small test case

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

    Leave a Reply

    Your email address will not be published. Required fields are marked *