Nth magical number

Math Binary Search

36.4% acceptance

Feb 22, 2026

1336

171

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

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

/*
 * 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 109 + 7.
 * Example 1:
 * Input: n = 1, a = 2, b = 3
 * Output: 2
 * Example 2:
 * Input: n = 4, a = 2, b = 3
 * Output: 6
 * Constraints:
 * 1 <= n <= 109
 * 2 <= a, b <= 4 * 104
 */

impl Solution {
  pub fn nth_magical_number(n: i32, a: i32, b: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let (a, b, n) = (a as i64, b as i64, n as i64);
    let g = { let (mut x, mut y) = (a, b); while y != 0 { let t = y; y = x % y; x = t; } x };
    let lcm = a / g * b;
    let count = |x: i64| x / a + x / b - x / lcm;
    let mut lo = 1i64;
    let mut hi = n * a.min(b);
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if count(mid) >= n { hi = mid; } else { lo = mid + 1; }
    }
    (lo % MOD) as i32
  }
}