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

Solution: Nth Magical Number

Understand how to find the nth magical number divisible by either of two integers by applying the inclusion-exclusion principle and binary search. This lesson guides you through implementing an efficient algorithm using mathematical insights and modular operations to solve large inputs optimally.

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