Ugly Number II

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...

Note that 1 is typically treated as an ugly number.

Example:

If n=9, return 10.

Solution:

We use three pointers to indicate the latest used numbers for multiplying with 2, 3 and 5 respectively. The smallest product among them are chosen as the new ugly number in the list. Until n ugly numbers are found. O(n) Space: O(n)

Code:

class Solution {
    public int nthUglyNumber(int n) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        for (int i = 1; i < n; i++) {
            int lastNum = list.get(list.size() - 1);
            while (list.get(p2) * 2 <= lastNum) {
                p2++;
            }
            while (list.get(p3) * 3 <= lastNum) {
                p3++;
            }
            while (list.get(p5) * 5 <= lastNum) {
                p5++;
            }
            list.add(Math.min(
                Math.min(list.get(p2) * 2, list.get(p3) * 3), list.get(p5) * 5
            ));
        }
        return list.get(n - 1);
    }
};