Is Nth Magical Number easy or hard?

Nth Magical Number is classified as Hard on LeetCode. The difficulty comes from recognizing that direct generation is inefficient and that the problem can be transformed into a counting function solved with binary search and LCM math.

Nth Magical Number Python/Java solution

Most implementations compute gcd, derive lcm(a,b), and perform binary search over the range [1, n * min(a,b)]. The same logic works in Python, Java, C++, C#, and JavaScript because it only uses integer arithmetic and loops.

How to solve Nth Magical Number in O(log n)?

Use binary search on the numeric range instead of generating numbers. For each midpoint, compute how many integers ≤ mid are divisible by a or b using inclusion-exclusion with LCM. Adjust the search range based on whether the count is smaller or larger than n until the smallest valid value is found.

What is the best approach for Nth Magical Number?

The optimal approach uses binary search combined with an LCM counting trick. For a candidate value x, count how many numbers ≤ x are divisible by a or b using x/a + x/b − x/lcm(a,b). Binary search finds the smallest x where this count is at least n. This runs in O(log(n * min(a,b))) time with constant space.

Is Nth Magical Number asked at Google/Amazon/Meta?

Variants of this problem appear in interviews at companies like Google and Amazon because it combines number theory with binary search. It tests understanding of LCM, GCD, inclusion-exclusion, and searching over monotonic functions.

What data structure is used in Nth Magical Number?

The optimal solution does not require a complex data structure. It relies on mathematical counting with LCM and a binary search over integers. A min-heap can also be used in an alternative approach to generate multiples in sorted order.

What is the time complexity of Nth Magical Number?

The optimal binary search solution runs in O(log(n * min(a,b))) time because the search range is bounded by n * min(a,b). Each step performs constant-time arithmetic operations including gcd and division. Space complexity is O(1).

Description Solution Video 23:10

878. Nth Magical Number

Hard37.1% acceptance3 companies

A positive integer is magical if it is divisible by either a or b.

Given the three integers n, a, and b, return the n^th magical number. Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 1, a = 2, b = 3
Output: 2

Example 2:

Input: n = 4, a = 2, b = 3
Output: 6

Constraints:

1 <= n <= 10⁹
2 <= a, b <= 4 * 10⁴

Asked at 3 companies

Amazon

Google Meta

Topics

Binary Search Math

23:10

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

1
2
3

Input

4
2
3

Your code is saved on this device.Solution