Ugly Number II
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
Check each number starting from 1 and verify if it's an ugly number by dividing it by 2, 3, and 5 until we find the nth ugly number.
Algorithm
- Initialize count = 1 and num = 1
- While count < n:
- Increment num
- Check if num is ugly:
- While num is divisible by 2, divide by 2
- While num is divisible by 3, divide by 3
- While num is divisible by 5, divide by 5
- If final number is 1, it's ugly
- If num is ugly, increment count
- Return num
Walkthrough
In this approach, we iterate through numbers starting from 1 and check if each number is an ugly number. A number is considered ugly if after dividing it by 2, 3, and 5 as many times as possible, we get 1.
public int nthUglyNumber(int n) { int count = 1; int num = 1; while (count < n) { num++; if (isUgly(num)) { count++; } } return num;} private boolean isUgly(int num) { if (num <= 0) return false; while (num % 2 == 0) num /= 2; while (num % 3 == 0) num /= 3; while (num % 5 == 0) num /= 5; return num == 1;}This solution checks each number sequentially until it finds the nth ugly number. For each number, we check if it's ugly by continuously dividing by 2, 3, and 5 until we either get 1 (ugly number) or a number that's not divisible by any of these primes (not an ugly number).
Complexity
Time
O(n * log n) - We need to check n numbers and for each number, we perform divisions
Space
O(1) - Only using a constant amount of extra space
Trade-offs
Pros
Simple to understand and implement
Works for small values of n
No extra space required except for variables
Cons
Very inefficient for large values of n
Checks many numbers that are not ugly
Performs redundant calculations
Solutions
Solution
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]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.