Problem Description

Given four integers N, A, and B, you are asked to find the Nth "magical number". A "magical number" is defined as a positive integer that is divisible by either A or B.

• The sequence of magical numbers is the list of all positive integers divisible by A or B, sorted in increasing order and without duplicates.
• You must return the Nth such number, modulo 10^9 + 7.
• Constraints guarantee that there is always exactly one valid answer for the given inputs.
• Values: 1 ≤ N ≤ 10^9, 2 ≤ A, B ≤ 4 × 10^4.

Thought Process

At first glance, you might consider generating all the numbers divisible by A or B in order, and picking the Nth one. However, given that N can be as large as 10^9, this brute-force approach is far too slow.

We need to find a more efficient way to determine the Nth magical number without generating the entire sequence. The key insight is to reframe the problem: instead of finding the Nth element by enumeration, ask: "For a given number X, how many magical numbers are less than or equal to X?" This allows us to use a binary search to efficiently home in on the answer.

Solution Approach

• Step 1: Counting Magical Numbers Up to X
  For any integer X, the number of magical numbers less than or equal to X is:
  • Count of multiples of A: floor(X / A)
  • Count of multiples of B: floor(X / B)
  • But numbers divisible by both A and B (i.e., by LCM(A, B)) are counted twice, so subtract floor(X / LCM(A, B))

  So, count(X) = floor(X / A) + floor(X / B) - floor(X / LCM(A, B)).

• Step 2: Binary Search
  We want the smallest X such that count(X) ≥ N. We can perform a binary search between min(A, B) and N * min(A, B) (since the Nth magical number can't be larger than N times the smallest of A or B).
• Step 3: LCM Calculation
  To avoid double counting, we need the least common multiple (LCM) of A and B. The LCM can be found as LCM(A,B) = (A * B) / GCD(A,B).
• Step 4: Modulo Operation
  Since the result can be very large, return the answer modulo 10^9 + 7.

Example Walkthrough

Let's walk through an example: N = 5, A = 2, B = 4.

• Step 1: List magical numbers up to the answer for clarity:
  Multiples of 2: 2, 4, 6, 8, 10, ...
  Multiples of 4: 4, 8, 12, ...
  Merged and sorted: 2, 4, 6, 8, 10, ...
  The first 5 magical numbers: 2, 4, 6, 8, 10. The 5th is 10.
• Step 2: Use binary search to find the answer:
  • LCM(2, 4) = 4
  • Start binary search between 2 and 10 (5 * 2).
  • Check mid = 6: count(6) = 6//2 + 6//4 - 6//4 = 3 + 1 - 1 = 3 (too small)
  • Check mid = 8: count(8) = 4 + 2 - 2 = 4 (still too small)
  • Check mid = 9: count(9) = 4 + 2 - 2 = 4
  • Check mid = 10: count(10) = 5 + 2 - 2 = 5 (just right!)

  Binary search identifies 10 as the smallest number with at least 5 magical numbers ≤ it.

Time and Space Complexity

• Brute-force Approach:
  Generating each magical number and counting up to N would take O(N) time and O(1) space. This is infeasible for large N.
• Optimized Approach (Binary Search):
  
  • Each binary search step computes counts in O(1) time.
  • The search range is up to N * min(A, B), so the number of steps is O(log(N * min(A, B))) ≈ O(log N).
  • Space complexity remains O(1) as only a few variables are used.

Summary

The key insight for the Nth Magical Number problem is to avoid brute-force enumeration by using a counting function and binary search. By counting how many magical numbers are ≤ X, and adjusting X using binary search, we efficiently find the answer even for very large N. The use of LCM ensures we don't double-count numbers divisible by both A and B. This approach is elegant, efficient, and leverages classic algorithmic techniques.

Code Implementation

import math

class Solution:
    def nthMagicalNumber(self, N: int, A: int, B: int) -> int:
        MOD = 10**9 + 7
        def lcm(x, y):
            return x * y // math.gcd(x, y)
        
        L = lcm(A, B)
        left, right = 1, N * min(A, B)
        while left < right:
            mid = (left + right) // 2
            # Count how many magical numbers ≤ mid
            if mid // A + mid // B - mid // L < N:
                left = mid + 1
            else:
                right = mid
        return left % MOD
      

class Solution {
public:
    int nthMagicalNumber(int N, int A, int B) {
        const int MOD = 1e9 + 7;
        long long lcm = (long long)A * B / std::__gcd(A, B);
        long long left = 1, right = (long long)N * std::min(A, B);
        while (left < right) {
            long long mid = left + (right - left) / 2;
            if (mid / A + mid / B - mid / lcm < N)
                left = mid + 1;
            else
                right = mid;
        }
        return left % MOD;
    }
};
      

class Solution {
    public int nthMagicalNumber(int N, int A, int B) {
        int MOD = 1000000007;
        long lcm = (long)A * B / gcd(A, B);
        long left = 1, right = (long)N * Math.min(A, B);
        while (left < right) {
            long mid = left + (right - left) / 2;
            if (mid / A + mid / B - mid / lcm < N) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return (int)(left % MOD);
    }
    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}
      

var nthMagicalNumber = function(N, A, B) {
    const MOD = 1e9 + 7;
    function gcd(a, b) {
        while (b !== 0) {
            let temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    function lcm(a, b) {
        return a * b / gcd(a, b);
    }
    let L = lcm(A, B);
    let left = 1, right = N * Math.min(A, B);
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (Math.floor(mid / A) + Math.floor(mid / B) - Math.floor(mid / L) < N)
            left = mid + 1;
        else
            right = mid;
    }
    return left % MOD;
};