Algorithm
Problem Name: 264. Ugly Number II
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return the nth 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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int nthUglyNumber(int n) {
int i, u2, u3, u5, k2, k3, k5, k;
int *p, sz;
p = malloc(n * sizeof(int));
//assert(p);
p[0] = 1;
u2 = u3 = u5 = 0;
for (i = 1; i < n; i ++) { // more like dp solution, 3ms
k2 = p[u2] * 2;
k3 = p[u3] * 3;
k5 = p[u5] * 5;
k = k2 < k3 ? k2 : k3;
k = k < k5 ? k : k5;
if (k == k2) u2 ++;
if (k == k3) u3 ++;
if (k == k5) u5 ++;
p[i] = k;
}
k = p[n - 1];
free(p);
return k;
}
Input
n = 10
Output
12
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int nthUglyNumber(int n) {
vector<int>dp(n);
dp[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for(int i = 1; i < n; i++){
dp[i] = min(dp[p2] * 2, 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 dp[n - 1];
}
};
Input
n = 10
Output
12
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int nthUglyNumber(int n) {
int[] arr = new int[n];
arr[0] = 1;
int idx2 = 0;
int idx3 = 0;
int idx5 = 0;
int mul2 = 2;
int mul3 = 3;
int mul5 = 5;
int ugly = arr[0];
for (int i = 1; i < n; i++) {
ugly = Math.min(mul2, Math.min(mul3, mul5));
arr[i] = ugly;
if (ugly == mul2) {
idx2++;
mul2 = arr[idx2] * 2;
}
if (ugly == mul3) {
idx3++;
mul3 = arr[idx3] * 3;
}
if (ugly == mul5) {
idx5++;
mul5 = arr[idx5] * 5;
}
}
return ugly;
}
}
Input
n = 1
Output
1
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const nthUglyNumber = function (n) {
if (n <= 0) return false
if (n === 1) return true
let t2 = 0,
t3 = 0,
t5 = 0
const k = Array(n).fill(1)
k[0] = 1
for (let i = 1; i < n; i++) {
k[i] = Math.min(k[t2] * 2, k[t3] * 3, k[t5] * 5)
if (k[i] == k[t2] * 2) t2++
if (k[i] == k[t3] * 3) t3++
if (k[i] == k[t5] * 5) t5++
}
return k[n - 1]
}
Input
n = 1
Output
1
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def nthUglyNumber(self, n):
arr, heap, used = [], [1], set()
for i in range(n):
num = heapq.heappop(heap)
arr.append(num)
for p in (2, 3, 5):
if p * num not in used:
heapq.heappush(heap, p * num)
used.add(p * num)
return arr[-1]
Input
n = 10
Output
12
#6 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0264_UglyNumberII
{
private readonly int[] numbers = new int[1690];
public int NthUglyNumber(int n)
{
if (n < 0) return -1;
if (n == 1) return 1;
if (numbers[n - 1] > 0) return numbers[n - 1];
int index2 = 0, index3 = 0, index5 = 0;
numbers[0] = 1;
for (int i = 1; i < n; i++)
{
numbers[i] = Math.Min(Math.Min(numbers[index2] * 2, numbers[index3] * 3), numbers[index5] * 5);
if (numbers[i] == numbers[index2] * 2) index2++;
if (numbers[i] == numbers[index3] * 3) index3++;
if (numbers[i] == numbers[index5] * 5) index5++;
}
return numbers[n - 1];
}
}
}
Input
n = 10
Output
12