Ugly Number II - Practice Coding Problems

Ugly Number II - Problem

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.

For example, the first 10 ugly numbers are: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12. Note that 1 is typically treated as an ugly number.

Input & Output

Example 1 — Finding 10th Ugly Number

$ Input: n = 10

› Output: 12

💡 Note: The first 10 ugly numbers are: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12. The 10th ugly number is 12.

Example 2 — First Ugly Number

$ Input: n = 1

› Output: 1

💡 Note: 1 is conventionally treated as the first ugly number.

Example 3 — Edge Case with Small n

$ Input: n = 6

› Output: 6

💡 Note: The first 6 ugly numbers are: 1, 2, 3, 4, 5, 6. The 6th is 6 (which is 2 × 3).

Constraints

1 ≤ n ≤ 1690

Visualization

Tap to expand

Understanding the Visualization

Input

Given n, find the nth ugly number

Generate

Build sequence using only factors 2, 3, 5

Output

Return the nth number in the sequence

Key Takeaway

🎯 Key Insight: Generate ugly numbers in order using three pointers for multiples of 2, 3, and 5

Asked in

G Google 25 a Amazon 20 M Microsoft 15 f Facebook 12

The key insight is to generate ugly numbers in ascending order rather than checking every number. The optimal DP approach uses three pointers to efficiently produce the sequence by always choosing the minimum next candidate. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming (Three Pointers)	O(n)	O(n)	Use three pointers to generate ugly numbers in ascending order efficiently
Brute Force	O(n * m)	O(1)	Check each number starting from 1 until we find n ugly numbers
Priority Queue (Min Heap)	O(n log n)	O(n)	Use a min heap to generate ugly numbers in ascending order

Dynamic Programming (Three Pointers) — Algorithm Steps

Initialize dp array with first ugly number (1)
Use three pointers i2, i3, i5 for multiples of 2, 3, 5
At each step, calculate next candidates: dp[i2]*2, dp[i3]*3, dp[i5]*5
Choose minimum and advance corresponding pointer(s)

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with dp[0]=1, three pointers at 0

Calculate

Find min of dp[i2]*2, dp[i3]*3, dp[i5]*5

Advance

Move pointer(s) that produced the minimum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int min(int a, int b, int c) {
    int temp = a < b ? a : b;
    return temp < c ? temp : c;
}

int solution(int n) {
    int* dp = malloc(sizeof(int) * n);
    dp[0] = 1;
    
    int i2 = 0, i3 = 0, i5 = 0;
    
    for (int i = 1; i < n; i++) {
        int next2 = dp[i2] * 2;
        int next3 = dp[i3] * 3;
        int next5 = dp[i5] * 5;
        
        dp[i] = min(next2, next3, next5);
        
        if (dp[i] == next2) i2++;
        if (dp[i] == next3) i3++;
        if (dp[i] == next5) i5++;
    }
    
    int result = dp[n - 1];
    free(dp);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single loop running n times, each iteration takes constant time

✓ Linear Growth

Space Complexity

O(n)

DP array storing n ugly numbers

⚡ Linearithmic Space

185.0K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming (Three Pointers) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler