Saturday, July 28, 2018

Leetcode 878. Nth Magical Number

A positive integer is magical if it is divisible by either A or B.
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

    Code (Java):
    class Solution {
        public int nthMagicalNumber(int N, int A, int B) {
            long lo = 2;
            long hi = Long.MAX_VALUE;
            
            while (lo < hi) {
                long mid = lo + (hi - lo) / 2;
                
                long lcm = A * B / gcd(A, B);
                
                long count = mid / A + mid / B - mid / lcm;
                
                if (count < N) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            
            long module = (long) Math.pow(10, 9) + 7;
            return (int)(lo % module);
        }
        
        private long gcd(long a, long b) {
            if (b == 0) {
                return a;
            }
            
            return gcd(b, a % b);
        }
    }
    

    1 comment: