# Nth Magical Number
**Difficulty:** HARD
[External](https://leetcode.com/problems/nth-magical-number)
Canonical: https://scaleengineer.com/dsa/problems/nth-magical-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
---
## 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 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`

# Approaches
## Brute Force Iteration
This is the most straightforward and naive approach. We can simply iterate through all positive integers, starting from 1. For each integer, we check if it's a magical number (i.e., divisible by `a` or `b`). We use a counter to keep track of how many magical numbers we have found. When the counter reaches `n`, the current integer is our answer.
**Time:** O(n * min(a, b)) - The n-th magical number can be as large as `n * min(a, b)`. The loop runs up to this value, making it prohibitively slow for large `n`. · **Space:** O(1) - Constant space is used as we only need a few variables to store the current number and the count.
**Pros:** Very simple to understand and implement.; Requires minimal mathematical insight.
**Cons:** Extremely inefficient for large values of `n`.; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.
### Explanation
The algorithm works by simulating the process of finding magical numbers one by one. It starts checking from `num = 1`. In a loop, it tests the condition `num % a == 0 || num % b == 0`. If this condition is true, we've found a magical number, so we increment a counter. We repeat this process, incrementing `num` each time, until our counter reaches the target `n`. The value of `num` at that point is the `n`-th magical number. While simple, its performance is directly tied to the magnitude of the final answer, which can be very large.

```java
class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        long MOD = 1_000_000_007;
        long num = 1;
        int count = 0;

        while (count < n) {
            if (num % a == 0 || num % b == 0) {
                count++;
            }
            if (count == n) {
                return (int)(num % MOD);
            }
            num++;
        }

        return -1; // Should not be reached
    }
}
```
### Algorithm
- Initialize a counter `count` to 0 and a number `num` to 1.
- Start an infinite loop.
- In each iteration, check if `num` is divisible by `a` or `b`.
- If it is, increment `count`.
- If `count` becomes equal to `n`, it means `num` is the `n`-th magical number. Return `num % (10^9 + 7)`.
- If `count` is not yet `n`, increment `num` and continue to the next iteration.

## Simulation with Pointers
A more optimized approach than brute force is to generate the magical numbers directly instead of checking every integer. This can be viewed as merging two sorted lists: the list of multiples of `a` (`a, 2a, 3a, ...`) and the list of multiples of `b` (`b, 2b, 3b, ...`). We can maintain pointers to the current head of each list and, in each step, pick the smaller element, which is the next magical number in the combined sorted sequence.
**Time:** O(n) - The main loop runs exactly `n` times. This is a significant improvement but still insufficient for the given constraints. · **Space:** O(1) - Only a few variables are needed for the pointers and the result, so space is constant.
**Pros:** Much more efficient than the brute-force approach.; Directly generates the required sequence without unnecessary checks.
**Cons:** The time complexity is linear with `n`, which is too slow for `n` up to 10^9.; Will also result in a 'Time Limit Exceeded' (TLE) error.
### Explanation
This method avoids checking non-magical numbers. We use two `long` variables, `pA` and `pB`, to keep track of the next available multiple of `a` and `b`. We loop `n` times. In each step, we find the minimum of `pA` and `pB`. This minimum is the next magical number. If they are equal, we've found a common multiple, which is counted as a single magical number. We then advance the pointer(s) that produced the minimum value. After `n` such steps, we will have found the `n`-th magical number.

```java
class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        long MOD = 1_000_000_007;
        long pA = a;
        long pB = b;
        long magicalNum = 0;

        for (int i = 1; i <= n; i++) {
            if (pA < pB) {
                magicalNum = pA;
                pA += a;
            } else if (pB < pA) {
                magicalNum = pB;
                pB += b;
            } else { // pA == pB, a common multiple
                magicalNum = pA;
                pA += a;
                pB += b;
            }
        }
        
        return (int)(magicalNum % MOD);
    }
}
```
### Algorithm
- Initialize two pointers, `pA` to `a` and `pB` to `b`. These represent the next multiple of `a` and `b` in their respective sequences.
- Loop from 1 to `n`.
- In each iteration, determine the next magical number by comparing `pA` and `pB`.
  - If `pA < pB`, the next magical number is `pA`. Update `pA` to the next multiple: `pA += a`.
  - If `pB < pA`, the next magical number is `pB`. Update `pB` to the next multiple: `pB += b`.
  - If `pA == pB`, it's a common multiple. The magical number is `pA`. Advance both pointers: `pA += a` and `pB += b`.
- After `n` iterations, the last found magical number is the answer. Return it modulo `10^9 + 7`.

## Binary Search with Mathematical Insight
Since the sequence of magical numbers is monotonically increasing, we can use binary search to find the `n`-th term efficiently. The core idea is to search for the answer `x` in a range of possible values. For any given `x`, we need a way to quickly determine how many magical numbers are less than or equal to `x`. This can be done with a mathematical formula based on the Principle of Inclusion-Exclusion.
**Time:** O(log(n * min(a, b))) - The binary search operates on a range up to `n * min(a, b)`. The GCD calculation is also logarithmic. This is very fast. · **Space:** O(1) - The algorithm uses a fixed amount of space regardless of the input size.
**Pros:** Extremely efficient, with logarithmic time complexity.; The only approach that can pass the given constraints for large `n`.
**Cons:** More complex to understand and implement compared to simulation.; Requires knowledge of number theory (GCD, LCM) and the binary search algorithm.
### Explanation
The number of integers up to `x` divisible by `a` is `x/a`. Similarly, for `b`, it's `x/b`. If we simply add these, `x/a + x/b`, we double-count the numbers divisible by both `a` and `b`. These are the multiples of the Least Common Multiple (LCM) of `a` and `b`. So, the correct count of magical numbers up to `x` is `count(x) = x/a + x/b - x/lcm(a, b)`. With this `count` function, we can binary search for the smallest `x` such that `count(x)` is at least `n`. This `x` will be our `n`-th magical number.

```java
class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        long MOD = 1_000_000_007;

        // Calculate LCM
        long longA = a;
        long longB = b;
        long commonDivisor = gcd(longA, longB);
        long lcm = (longA * longB) / commonDivisor;

        // Binary search for the answer
        long low = 1;
        long high = (long)n * Math.min(a, b); // A safe upper bound
        long ans = 0;

        while (low <= high) {
            long mid = low + (high - low) / 2;
            
            // Calculate how many magical numbers are <= mid
            long count = mid / a + mid / b - mid / lcm;

            if (count >= n) {
                ans = mid; // This is a potential answer
                high = mid - 1; // Try to find a smaller one
            } else {
                low = mid + 1; // mid is too small
            }
        }

        return (int)(ans % MOD);
    }

    // Helper function to compute GCD using Euclidean algorithm
    private long gcd(long x, long y) {
        while (y != 0) {
            long temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }
}
```
### Algorithm
- First, create a helper function `gcd(x, y)` to compute the Greatest Common Divisor using the Euclidean algorithm.
- Calculate the Least Common Multiple (LCM) of `a` and `b` using the formula `lcm = (a * b) / gcd(a, b)`. Use `long` to prevent overflow.
- The number of magical numbers less than or equal to some value `x` is given by the Inclusion-Exclusion Principle: `count(x) = x/a + x/b - x/lcm`.
- Perform a binary search on the possible range of answers. The lower bound `low` can be 1, and a safe upper bound `high` is `n * min(a, b)`.
- In each step of the binary search:
  - Calculate `mid = low + (high - low) / 2`.
  - Compute `count(mid)`.
  - If `count(mid) >= n`, then `mid` is a potential answer. We store it and try to find a smaller answer by setting `high = mid - 1`.
  - If `count(mid) < n`, then `mid` is too small, so we search in the upper half by setting `low = mid + 1`.
- The loop terminates when `low > high`, and the last valid answer found is the `n`-th magical number. Return this answer modulo `10^9 + 7`.

# Solutions
### Java

```java
class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int nthMagicalNumber ( int n , int a , int b ) { int c = a * b / gcd ( a , b ); long l = 0 , r = ( long ) ( a + b ) * n ; while ( l < r ) { long mid = l + r >>> 1 ; if ( mid / a + mid / b - mid / c >= n ) { r = mid ; } else { l = mid + 1 ; } } return ( int ) ( l % MOD ); } private int gcd ( int a , int b ) { return b == 0 ? a : gcd ( b , a % b ); } }
```

### CPP

```cpp
using ll = long long ; class Solution { public: const int mod = 1e9 + 7 ; int nthMagicalNumber ( int n , int a , int b ) { int c = lcm ( a , b ); ll l = 0 , r = 1ll * ( a + b ) * n ; while ( l < r ) { ll mid = l + r >> 1 ; if ( mid / a + mid / b - mid / c >= n ) r = mid ; else l = mid + 1 ; } return l % mod ; } };
```

### Python

```python
class Solution : def nthMagicalNumber ( self , n : int , a : int , b : int ) -> int : mod = 10 ** 9 + 7 c = lcm ( a , b ) r = ( a + b ) * n return bisect_left ( range ( r ), x = n , key = lambda x : x // a + x // b - x // c ) % mod
```