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
Use dynamic programming to generate ugly numbers in order by maintaining three pointers for multiplying with 2, 3, and 5.
Algorithm
- Create dp array of size n and initialize dp[0] = 1
- Initialize three pointers p2, p3, p5 = 0
- For i from 1 to n-1:
- Calculate next2 = dp[p2] * 2
- Calculate next3 = dp[p3] * 3
- Calculate next5 = dp[p5] * 5
- Set dp[i] = min(next2, next3, next5)
- Increment pointers corresponding to the minimum value used
- Return dp[n-1]
Walkthrough
This approach uses dynamic programming to generate ugly numbers in sequence. We maintain three pointers pointing to the previous numbers that need to be multiplied by 2, 3, and 5 respectively. At each step, we take the minimum of these three products to get the next ugly number.
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; int next3 = dp[p3] * 3; int next5 = dp[p5] * 5; int nextUgly = Math.min(next2, Math.min(next3, next5)); dp[i] = nextUgly; if (nextUgly == next2) p2++; if (nextUgly == next3) p3++; if (nextUgly == next5) p5++; } return dp[n-1];}The solution maintains an array dp where dp[i] represents the (i+1)th ugly number. We use three pointers p2, p3, and p5 to keep track of which previous ugly number should be multiplied by 2, 3, and 5 respectively. At each step, we take the minimum of these three products to get the next ugly number.
Complexity
Time
O(n) - We only need to iterate through the array once
Space
O(n) - We need an array to store n ugly numbers
Trade-offs
Pros
Generates ugly numbers in sequence without checking unnecessary numbers
Much more efficient than brute force approach
Each ugly number is calculated exactly once
Cons
Requires extra space to store all ugly numbers
May not be suitable for very large values of n due to memory constraints
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]; }}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 ]; } }/** * @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];};class Solution : def nthUglyNumber ( self , n : int ) -> int : if n <= 0 : return 0 nums = [ 1 ] i2 , i3 , i5 = 0 , 0 , 0 while len ( nums ) < n : m2 = nums [ i2 ] * 2 m3 = nums [ i3 ] * 3 m5 = nums [ i5 ] * 5 mn = min ( m2 , m3 , m5 ) nums . append ( mn ) if mn == m2 : i2 += 1 if mn == m3 : # Note: 3*2 and 2*3 are both 6, so cannot use elif i3 += 1 if mn == m5 : i5 += 1 return nums [ - 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 : 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 ( 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 ]// 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 (); } };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.