Skip to main content

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

Comments

Post a Comment

Popular posts from this blog

Brute Force - Question 2

2105. Watering Plants II Alice and Bob want to water n plants in their garden. The plants are arranged in a row and are labeled from 0 to n - 1 from left to right where the ith plant is located at x = i. Each plant needs a specific amount of water. Alice and Bob have a watering can each, initially full. They water the plants in the following way: Alice waters the plants in order from left to right, starting from the 0th plant. Bob waters the plants in order from right to left, starting from the (n - 1)th plant. They begin watering the plants simultaneously. It takes the same amount of time to water each plant regardless of how much water it needs. Alice/Bob must water the plant if they have enough in their can to fully water it. Otherwise, they first refill their can (instantaneously) then water the plant. In case both Alice and Bob reach the same plant, the one with more water currently in his/her watering can should water this plant. If they have the same amount of water, then Alice ...
Post a Comment
Read more

Sliding Window - Question 1

Leetcode 76. Minimum Window Substring Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "". The testcases will be generated such that the answer is unique. A substring is a contiguous sequence of characters within the string. Constraints: m == s.length n == t.length 1 <= m, n <= 10^5 s and t consist of uppercase and lowercase English letters. Analysis: The first step to do is to count the letters in string t, since the relative order of chars does not matter. After the counting, we can use two pointers method on string s: starting with beginning of the string s, the second pointer can continue to move until the sub-string [i, j) has all the chars in t, where i the index of the first pointer, and j is the index of the second pointer. We are looking for the sub-string with the minimum leng...
Post a Comment
Read more