Binary Search - Hard Level - Question 3

Binary Search - Hard Level - Question 3

878. Nth Magical Number

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 10^9 + 7.

Analysis:

Let us consider some examples first.

Example 1, a = 4, b = 2. If b is dividable by a, then all the numbers which is dividable by a should be dividable by b as well. So the nth magical number should be n*b;

Example 2, a = 3, b = 2.

The multiples of 2 are: 2, 4, 6, 8, 10, 12, ...

The multiple of 3 are: 3, 6, 9, 12, ...

So the overlap is related to the minimum common multiple between a and b, and we need to remove the overlap which is double-counted.

So now, we make some conclusions:

1. the upper bound of the nth magical number should be n*b, where a is the smaller one (or b <= a);

2. there are n*b/a magical numbers smaller than n*b;

3. there are n*b/(minimum common multiple) overlaps.

Thus, the overall count is: n + n*b/a - n*b/(minimum common multiple).

This is monotonically increasing function of n, so we can use binary search to determine the minimum value of n.

One detail to about the boundary: for example, 10 is 7th magical number of 2 and 3. Then how about the 6th? In this case, we need to check whether the minimum value of multiple of a is jus the nth or (n+1)th magical number. If it is the (n+1)th, then we need to use the closest multiple of b.

In the above example, from the binary search, n = 5. So the value is 5*2 = 10. However, there are 7 multiples <= 10. So 10 is the 7th magical number, not the 6th. The 6th magical number is 5*2/3*3 = 9.

See the code below:

class Solution {
public:
    int nthMagicalNumber(int n, int a, int b) {
        if(a<b) return nthMagicalNumber(n, b, a);
        int l = 1, r = n, mod = 1e9 + 7;
        long c = gcd(a, b), d = (long)a*(long)b/c;
        if(c == b) return (long)r*b%mod;
        while(l < r) {
            int mid = l + (r - l) / 2;
            int ct = count(mid, a, b, d);
            if(ct < n) l = mid + 1;
            else r = mid;
        }
        if(count(l, a, b, d) > n) return (long)l*b/a*a%mod;
        return (long)l*b%mod;
    }
private:
    int gcd(int a, int b) {
        if(a < b) return gcd(b, a);
        if(b == 0) return a;
        return gcd(a%b, b);
    }
    int count(int mid, int a, int b, int d) {
        long v = (long)mid * b;
        return mid + v/a - v/d;
    }
};

Upper Layer