1201. Ugly Number III [TODO]

 一刷 06/2022

Version #1 LCM - Least common multiple

GCD - Greatest Common Divisor

非常好的一道题，再多做几遍[TODO]

Runtime: 1 ms, faster than 80.13% of Java online submissions for Ugly Number III.

Memory Usage: 41.3 MB, less than 15.71% of Java online submissions for Ugly Number III.

class Solution {

    public int nthUglyNumber(int n, int a, int b, int c) {

        long ab = lcm((long)a, (long)b);

        long ac = lcm((long)a, (long)c);

        long bc = lcm((long)b, (long)c);

        long abc = lcm(a, bc);

        // System.out.printf("abc=%d", abc);

        long start = 1;

        long end = Integer.MAX_VALUE;

        while (start < end) {

            long mid = start + (end - start) / 2;

            long result = mid / a + mid / b + mid / c - mid / ab - mid / ac - mid / bc + mid / abc;

            // There are multiple numbers satisfy that there a #result number of unly numbers smaller than or equals to that number

            // We want to find the first occurance, so we can't return directly when we found reuslt == n

            // if (result == n) {

            //     return mid;

            // } 

            if (result < n) {

                start = mid + 1;

            } else {

                end = mid;

            }

        }

        return (int)start;

    }

    

    private long lcm(long a, long b) {

        return (a * b) / gcd(a, b);

    }

    

    private long gcd(long a, long b) {

        if (b == 0) {

            return a;

        }

        return gcd(b, a % b);

    }

}