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 modulo10^9 + 7.

Examples

Example 1

1
2

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

Example 2

1
2

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

Constraints

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

Solution

Method 1 -

Intuition

We need to find the nth number divisible by either a or b. Direct simulation is too slow for large n. Instead, we use binary search and inclusion-exclusion to count how many numbers ≤ x are divisible by a or b.

Approach

Let L = lcm(a, b). For any x, the count of magical numbers ≤ x is (x // a) + (x // b) - (x // L). Use binary search to find the smallest x such that this count ≥ n. Return x modulo 1e9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int nthMagicalNumber(int n, int a, int b) {
    long mod = 1e9+7;
    long l = min(a, b), r = (long)n * min(a, b);
    long L = lcm(a, b);
    while (l < r) {
        long m = l + (r-l)/2;
        if (m/a + m/b - m/L < n) l = m+1;
        else r = m;
    }
    return l % mod;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
func nthMagicalNumber(n, a, b int) int {
    mod := int(1e9+7)
    l, r := min(a, b), n*min(a, b)
    L := a * b / gcd(a, b)
    for l < r {
        m := l + (r-l)/2
        if m/a + m/b - m/L < n {
            l = m + 1
        } else {
            r = m
        }
    }
    return l % mod
}
func min(a, b int) int { if a < b { return a } else { return b } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public int nthMagicalNumber(int n, int a, int b) {
    long mod = 1_000_000_007L;
    long l = Math.min(a, b), r = (long)n * Math.min(a, b);
    long L = lcm(a, b);
    while (l < r) {
        long m = l + (r-l)/2;
        if (m/a + m/b - m/L < n) l = m+1;
        else r = m;
    }
    return (int)(l % mod);
}
private long lcm(int a, int b) {
    return (long)a * b / gcd(a, b);
}
private int gcd(int a, int b) {
    while (b != 0) {
        int t = b; b = a % b; a = t;
    }
    return a;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

fun nthMagicalNumber(n: Int, a: Int, b: Int): Int {
    val mod = 1_000_000_007L
    var l = minOf(a, b).toLong()
    var r = n.toLong() * minOf(a, b)
    val L = lcm(a, b)
    while (l < r) {
        val m = l + (r-l)/2
        if (m/a + m/b - m/L < n) l = m+1
        else r = m
    }
    return (l % mod).toInt()
}
fun lcm(a: Int, b: Int): Long = a.toLong() * b / gcd(a, b)
fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def nthMagicalNumber(n: int, a: int, b: int) -> int:
    import math
    mod = 10**9 + 7
    l, r = min(a, b), n * min(a, b)
    L = a * b // math.gcd(a, b)
    while l < r:
        m = (l + r) // 2
        if m//a + m//b - m//L < n:
            l = m + 1
        else:
            r = m
    return l % mod
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn nth_magical_number(n: i32, a: i32, b: i32) -> i32 {
        fn gcd(mut a: i64, mut b: i64) -> i64 {
            while b != 0 {
                let t = b; b = a % b; a = t;
            }
            a
        }
        let mod_ = 1_000_000_007;
        let (a, b, n) = (a as i64, b as i64, n as i64);
        let l = a.min(b);
        let mut left = l;
        let mut right = n * l;
        let lcm = a * b / gcd(a, b);
        while left < right {
            let m = left + (right - left) / 2;
            if m/a + m/b - m/lcm < n {
                left = m + 1;
            } else {
                right = m;
            }
        }
        (left % mod_) as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

function gcd(a: number, b: number): number {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}
function nthMagicalNumber(n: number, a: number, b: number): number {
    const mod = 1e9 + 7;
    let l = Math.min(a, b), r = n * Math.min(a, b);
    const L = a * b / gcd(a, b);
    while (l < r) {
        const m = Math.floor((l + r) / 2);
        if (Math.floor(m/a) + Math.floor(m/b) - Math.floor(m/L) < n) l = m + 1;
        else r = m;
    }
    return l % mod;
}

Complexity

  • ⏰ Time complexity: O(log(n * min(a, b))) due to binary search.
  • 🧺 Space complexity: O(1).