Skip to main content

878. Nth Magical Number

hard

A 'magical number' is divisible by a or b. Find the nth such positive integer modulo 10^9 + 7. Binary search on the answer combined with inclusion-exclusion is the textbook attack.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

A positive integer is magical if it is divisible by either a or b. Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 10^9 + 7.

Constraints

  • 1 <= n <= 10^9
  • 2 <= a, b <= 4 * 10^4

Examples

Example 1

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

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Count(x) = number of magical integers in [1, x] = floor(x/a) + floor(x/b) - floor(x/lcm(a,b)). Inclusion-exclusion.

Hint 2

Count(x) is non-decreasing in x. Find the smallest x with Count(x) >= n via binary search.

Hint 3

Search range: [1, n * min(a, b)] — that's a safe upper bound because every multiple of min(a, b) contributes.

Hint 4

Apply modulo 10^9 + 7 only at the very end on the answer.

Solution approach

Reveal approach

Binary search on the answer. Let lcm = a * b / gcd(a, b). Define count(x) = x/a + x/b - x/lcm using integer division — this counts integers in [1, x] divisible by a or b via inclusion-exclusion. count(x) is non-decreasing in x, so the smallest x with count(x) >= n is the nth magical number. Search range [1, n * min(a, b)] is safe. Inside the loop: mid = lo + (hi - lo) / 2; if count(mid) < n, set lo = mid + 1; else hi = mid. When lo == hi, that's the answer. Return lo % (10^9 + 7). O(log(n * min(a, b))) iterations, each O(1) — effectively O(log n). O(1) space.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search
  • math
  • inclusion-exclusion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

Practice these live with InterviewChamp.AI

Drill Nth Magical Number and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →