Question

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

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the n^th ugly number.

Example 1:

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.

Example 2:

Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Constraints:

1 <= n <= 1690

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

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);
        }
    }
}

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

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i < n; ++i) {
            int next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5;
            dp[i] = Math.min(next2, Math.min(next3, next5));
            if (dp[i] == next2) ++p2;
            if (dp[i] == next3) ++p3;
            if (dp[i] == next5) ++p5;
        }
        return dp[n - 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]

############
from heapq import heappop

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(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]

func nthUglyNumber(n int) int {
	dp := make([]int, n)
	dp[0] = 1
	p2, p3, p5 := 0, 0, 0
	for i := 1; i < n; i++ {
		next2, next3, next5 := dp[p2]*2, dp[p3]*3, dp[p5]*5
		dp[i] = min(next2, min(next3, next5))
		if dp[i] == next2 {
			p2++
		}
		if dp[i] == next3 {
			p3++
		}
		if dp[i] == next5 {
			p5++
		}
	}
	return dp[n-1]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function (n) {
    let dp = [1];
    let p2 = 0,
        p3 = 0,
        p5 = 0;
    for (let i = 1; i < n; ++i) {
        const next2 = dp[p2] * 2,
            next3 = dp[p3] * 3,
            next5 = dp[p5] * 5;
        dp[i] = Math.min(next2, Math.min(next3, next5));
        if (dp[i] == next2) ++p2;
        if (dp[i] == next3) ++p3;
        if (dp[i] == next5) ++p5;
        dp.push(dp[i]);
    }
    return dp[n - 1];
};

public class Solution {
    public int NthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i < n; ++i) {
            int next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5;
            dp[i] = Math.Min(next2, Math.Min(next3, next5));
            if (dp[i] == next2) {
                ++p2;
            }
            if (dp[i] == next3) {
                ++p3;
            }
            if (dp[i] == next5) {
                ++p5;
            }
        }
        return dp[n - 1];
    }
}

264 - Ugly Number II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions