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 Sam K., 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

More Math practice problems

See all Math problems →