878 Nth Magical Number

878. 1. Question

A positive integer ismagical if it is divisible by eitherA orB.

Return the N-th magical number. Since the answer may be very large, return it modulo10^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 <= N <= 10^9
2 <= A <= 40000
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)是为了避免计算重复的数字

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)

Previous875 Koko Eating Bananas Next887 Super Egg Drop

Last updated 5 years ago

Was this helpful?

1. Question