Ugly Number II

Question

Ugly number is a number that only have factors 2, 3 and 5.

Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

Notice

Note that 1 is typically treated as an ugly number.

Example

If n = 9, return 10.

Challenge

O(n log n) or O(n) time.

Analysis

Dynamic Programming

有三个prime number 2，3，5，可以设想因为新的ugly number必然是此前已经知道的ugly number再乘以2 或3 或5。 对于uglyNumbers[0]，下一个uglyNumbers[1]，就将在uglyNumber[0] 2, uglyNumber[0] 3, uglyNumber[0] * 5 之中产生，其中最小的一个就是uglyNumbers[1]。接下来寻找uglyNumbers[2]时，对于2这个数来说，就需要选用uglyNumbers[1]来平衡所得乘积。重复这个过程直到第n个uglyNumber产生。 这种算法的时间复杂度是O(n)，因为只需要一次循环，对于每一个循环中ugly number的寻找是可以认为O(1)的。 注意的是起始条件的设定，uglyNumbers[0] = 1，和uglyNumbers[1] = 2，也就是current = 2。

“The ugly-number sequence is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … because every number can only be divided by 2, 3, 5, one way to look at the sequence is to split the sequence to three groups as below:

(1) 1×2, 2×2, 3×2, 4×2, 5×2, …
(2) 1×3, 2×3, 3×3, 4×3, 5×3, …
(3) 1×5, 2×5, 3×5, 4×5, 5×5, …

We can find that every subsequence is the ugly-sequence itself (1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 …) multiply 2, 3, 5.

Then we use similar merge method as merge sort, to get every ugly number from the three subsequence.

Every step we choose the smallest one, and move one step after,including nums with same value.”

Ref:

https://leetcode.com/problems/ugly-number-ii/discuss/69362/O(n)-Java-solution?orderBy=most_votes

https://www.geeksforgeeks.org/ugly-numbers/

PriorityQueue

也可以考虑用Heap，也就是将无重复的(de-duped) ugly number存入一个Min-Heap，运行poll() n - 1次，那么得到的就是第n个ugly number（1是第一个ugly number）。去除重复的办法有1. 利用HashMap/HashSet存储生成过的unique的ugly number，这样每次存入Heap时检查是否已经生成过了，确保只存入新的值 2. 在Heap poll()的时候，如果peek()下一个值和当前poll()的值相同，则继续poll()，直到peek()的值不同为止。

Solution

O(n) Scan

import java.util.ArrayList;

class Solution {
    /**
     * @param n an integer
     * @return the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        ArrayList<Integer> uglyNumbers = new ArrayList<Integer>();
        uglyNumbers.add(1);
        int p1 = 0;
        int p2 = 0;
        int p3 = 0;
        int current = 2;

        for (int i = 0; i < n; i++) {
            while (uglyNumbers.get(p1) * 2 < current) {
                p1++;
            }
            int min1 = uglyNumbers.get(p1) * 2;

            while (uglyNumbers.get(p2) * 3 < current) {
                p2++;
            }
            int min2 = uglyNumbers.get(p2) * 3;

            while (uglyNumbers.get(p3) * 5 < current) {
                p3++;
            }
            int min3 = uglyNumbers.get(p3) * 5;

            int next = Math.min(Math.min(min1, min2), min3);
            current = next + 1;
            uglyNumbers.add(next);
        }
        return uglyNumbers.get(n - 1);
    }
}

O(n) Scan 2

public class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        int factor2 = 2, factor3 = 3, factor5 = 5;
        for(int i=1;i<n;i++){
            int min = Math.min(Math.min(factor2,factor3),factor5);
            ugly[i] = min;
            if(factor2 == min)
                factor2 = 2*ugly[++index2];
            if(factor3 == min)
                factor3 = 3*ugly[++index3];
            if(factor5 == min)
                factor5 = 5*ugly[++index5];
        }
        return ugly[n-1];
    }
}

O(n) A more concise version

    public int nthUglyNumber(int n) {
        int[] nums = new int[n];
        int index2 = 0, index3 = 0, index5 = 0;
        nums[0] = 1;
        for(int i = 1; i < nums.length; i++){
            nums[i] = Math.min(nums[index2] * 2, Math.min(nums[index3] * 3, nums[index5] * 5));
            if(nums[i] == nums[index2] * 2)
                index2++;
            if(nums[i] == nums[index3] * 3)
                index3++;
            if(nums[i] == nums[index5] * 5)
                index5++;
        }
        return nums[n - 1];
    }

O(nlogn) HashMap + Heap (use HashMap to dedupe element in Heap)

class Solution {
    /**
     * @param n an integer
     * @return the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        // Write your code here
        Queue<Long> Q = new PriorityQueue<Long>();
        HashSet<Long> inQ = new HashSet<Long>();
        Long[] primes = new Long[3];
        primes[0] = Long.valueOf(2);
        primes[1] = Long.valueOf(3);
        primes[2] = Long.valueOf(5);
        for (int i = 0; i < 3; i++) {
            Q.add(primes[i]);
            inQ.add(primes[i]);
        }
        Long number = Long.valueOf(1);
        for (int i = 1; i < n; i++) {
            number = Q.poll();
            for (int j = 0; j < 3; j++) {
                if (!inQ.contains(primes[j] * number)) {
                    Q.add(number * primes[j]);
                    inQ.add(number * primes[j]);
                }
            }
        }
        return number.intValue();
    }
}

Heap - PriorityQueue

class Solution {
    public int nthUglyNumber(int n) {
        if(n <= 0){
            return 0;
        }

        PriorityQueue<Long> pq = new PriorityQueue<>();

        pq.offer(1l);

        for(int i = 0; i < n-1; i++){
            long tmp = pq.poll();

            while(!pq.isEmpty() && pq.peek() == tmp){
                tmp = pq.poll();
            }

            pq.offer(tmp * 2);
            pq.offer(tmp * 3);
            pq.offer(tmp * 5);
        }

        return pq.poll().intValue();
    }
}

DP + DFS (2ms AC)

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        return DFS(dp, 1, 0, 0, 0, n);
    }

    private int DFS(int[] dp, int i, int p2, int p3, int p5, int n) {
        if (i == n) return dp[n - 1];
        dp[i] = Math.min(dp[p2] * 2, Math.min(dp[p3] * 3, dp[p5] * 5));
        if (dp[i] == dp[p2] * 2) p2++;
        if (dp[i] == dp[p3] * 3) p3++;
        if (dp[i] == dp[p5] * 5) p5++;
        return DFS(dp, i + 1, p2, p3, p5, n);
    }
}