Question

Formatted question description: https://leetcode.ca/all/264.html

 264	Ugly Number II

 Write a program to find the n-th ugly number.

 Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

 Example:

 Input: n = 10
 Output: 12
 Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

 Note:
     1 is typically treated as an ugly number.
     n does not exceed 1690.

 @tag-array

Algorithm

Each sublist is an ugly number multiplied by 2, 3, 5,

The required ugly number is taken from the generated sequence,

Every time, the smallest one from the three lists is added to the sequence.

We can maintain three lists of ugly numbers:

1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2, 9*2
1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3, 8*3
1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5, 8*5

Carefully observe the above three lists, you can find that each sublist is an ugly number multiplied by 2, 3, 5, and the required ugly number is taken from the generated sequence, each time from the three lists to take out the smallest one to join the sequence.

Step by step example:

[1]
1,1,1

[1, 2]
2,1,1

[1, 2, 3]
2,2,1

[1, 2, 3, 4]
3,2,1

[1, 2, 3, 4, 5]
3,2,2

[1, 2, 3, 4, 5, 6]
4,3,2

[1, 2, 3, 4, 5, 6, 8]
5,3,2

[1, 2, 3, 4, 5, 6, 8, 9]
5,4,2

[1, 2, 3, 4, 5, 6, 8, 9, 10]
6,4,3

Code

Java

import java.util.ArrayList;
import java.util.List;

public class Ugly_Number_II {

    public static void main(String[] args) {
        Ugly_Number_II out = new Ugly_Number_II();
        Solution s = out.new Solution();

        System.out.println(s.nthUglyNumber(10));
    }

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

            List<Integer> nums = new ArrayList<>();
            nums.add(1);

            int i2 = 0;
            int i3 = 0;
            int i5 = 0;

            while (nums.size() < n) {

                int m2 = nums.get(i2) * 2;
                int m3 = nums.get(i3) * 3;
                int m5 = nums.get(i5) * 5;

                int mn = Math.min(Math.min(m2, m3), m5);
                nums.add(mn);

                if (mn == m2) {
                    i2++;
                }

                if (mn == m3) { // @note: 3*2 and 2*3 are both 6, so cannot else-if
                    i3++;
                }

                if (mn == m5) {
                    i5++;
                }
            }

            return nums.get(nums.size() - 1);
        }
    }
}

// OJ: https://leetcode.com/problems/ugly-number-ii/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> num(n);
        num[0] = 1;
        int i = 0, j = 0, k = 0;
        for (int t = 1; t < n; ++t) {
            num[t] = min({ num[i] * 2, num[j] * 3, num[k] * 5 });
            if (num[t] == num[i] * 2) ++i;
            if (num[t] == num[j] * 3) ++j;
            if (num[t] == num[k] * 5) ++k;
        }
        return num.back();
    }
};

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [1] * n
        p2 = p3 = p5 = 0
        for i in range(1, n):
            next2, next3, next5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
            dp[i] = min(next2, next3, next5)
            if dp[i] == next2:
                p2 += 1
            if dp[i] == next3:
                p3 += 1
            if dp[i] == next5:
                p5 += 1
        return dp[n - 1]

############

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        h = [1] # heap
        vis = {1} # hashtable to de-dup
        ans = 1
        for _ in range(n):
            ans = heappop(h)
            for v in [2, 3, 5]:
                nxt = ans * v
                if nxt not in vis:
                    vis.add(nxt)
                    heappush(h, nxt)
        return ans

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [1] * n
        p2 = p3 = p5 = 0
        for i in range(1, n):
            next2, next3, next5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
            dp[i] = min(next2, next3, next5)
            if dp[i] == next2:
                p2 += 1
            if dp[i] == next3:
                p3 += 1
            if dp[i] == next5:
                p5 += 1
        return dp[-1]

############

class Solution(object):
  def nthUglyNumber(self, n):
    """
    :type n: int
    :rtype: int
    """
    dp = [0] * (n + 1)
    dp[1] = 1
    i2 = i3 = i5 = 1
    for i in range(2, n + 1):
      dp[i] = min(dp[i2] * 2, dp[i3] * 3, dp[i5] * 5)
      if dp[i] == dp[i2] * 2:
        i2 += 1
      if dp[i] == dp[i3] * 3:
        i3 += 1
      if dp[i] == dp[i5] * 5:
        i5 += 1
    return dp[-1]

264 - Ugly Number II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions