Leetcode/src/main/java/com/fishercoder/solutions/_264.java at master · ernestp56/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package com.fishercoder.solutions;

public class _264 {

    public static class Solution1 {
        /**
         * credit: https://discuss.leetcode.com/topic/21791/o-n-java-solution
         */
        public int nthUglyNumber(int n) {
            int[] ugly = new int[n];
            ugly[0] = 1;
            int index2 = 0;
            int index3 = 0;
            int index5 = 0;
            int factor2 = 2;
            int factor3 = 3;
            int 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];
        }
    }
}