# 878     Nth Magical Number

## 878. [Nth Magical Number](https://leetcode.com/problems/nth-magical-number/description/)

## 1. Question

A positive integer is*magical* if it is divisible by eitherA orB.

Return the N-th magical number. Since the answer may be very large, **return it modulo**`10^9 + 7.`

**Example 1:**

```
Input: N = 1, A = 2, B = 3
Output: 2
```

**Example 2:**

```
Input: N = 4, A = 2, B = 3
Output: 6
```

**Example 3:**

```
Input: N = 5, A = 2, B = 4
Output: 10
```

**Example 4:**

```
Input: N = 3, A = 6, B = 4
Output: 8
```

**Note:**

1. `1 <= N <= 10^9`
2. `2 <= A <= 40000`
3. `2 <= B <= 40000`

## 2. Implementation

**(1) Binary Search**

思路：

要找出第N个数能被A或B除，我们可以用二分查找在\[Math.min(A, B), Long.MAX\_VALUE]的范围内找到。在二分查找的过程中，我们先判断如果target number是mid, 它有多少个magic number。如果magic number的数量小于N, 说明mid太小，则将范围缩小到\[mid + 1, end]， 否则mid太大，范围变为\[start, mid]。找magic number的个数，我们可以通过公式 x / A + x / B - x / (A \* B /gcd)得到，其中A \* B /gcd是A, B是最小公倍数， 减去x / (A \* B /gcd)是为了避免计算重复的数字

```java
class Solution {
    public int nthMagicalNumber(int N, int A, int B) {
        long start = Math.min(A, B);
        long end = Long.MAX_VALUE;
        long mod = (long)1e9 + 7;
        int gcd = getGCD(A, B);

        while (start + 1 < end) {
            long mid = start + (end - start) / 2;

            if (!isValid(A, B, N, gcd, mid)) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }

        return isValid(A, B, N, gcd, start) ? (int)(start % mod) : (int)(end % mod);
    }

    public int getGCD(int a, int b) {
        while (b > 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }

    public boolean isValid(int a, int b, int n, int gcd, long target) {
        return target / a + target / b - target / ((a * b) / gcd) >= n;
    }
}
```

## 3. Time & Space Complexity

**Binary Search:** 时间复杂度O(log(Max)), max表示的是Log.MAX\_VALUE, 空间复杂度O(1)