Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: Nth Magical Number

Understand how to compute the nth magical number, defined as a positive integer divisible by either of two given numbers. Explore the use of binary search combined with the inclusion-exclusion principle to efficiently solve this problem modulo 10^9+7 with optimal time and space complexity.

We'll cover the following...

Statement

Given three integers n, a, and b, return the nth magical number.

A magical number is defined as a positive integer that is divisible by either a or b.

As the result may be very large, return it modulo 109+710^9+7.

Constraints:

  • 1≤1 \leq n ≤109\leq 10^9

  • 2≤2 \leq a, b ≤4×104\leq 4 \times 10^4 ...