Problem statement

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. The sequence begins 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, …

Example 1

Input: n = 10
Output: 12

Example 2

Input: n = 1
Output: 1
Explanation: 1 is conventionally the first ugly number.

Example 3

Input: n = 7
Output: 8

Constraints

• 1 <= n <= 1000

Follow-up: Testing every integer for uglyness is far too slow. Can you generate the sequence directly?

Hints for Ugly Number II

1. Hint 1

   Every ugly number after 1 is an earlier ugly number multiplied by 2, 3 or 5.

2. Hint 2

   Keep three pointers into the list already built, one per multiplier, and always take the smallest candidate.

3. Hint 3

   Advance every pointer whose candidate equals the value just taken — otherwise duplicates like 6 appear twice.

How to solve Ugly Number II

Every ugly number after 1 is an earlier ugly number times 2, 3 or 5. Keep three pointers into the list built so far and always emit the smallest candidate.

Approach

1. Start ugly = [1] and i2 = i3 = i5 = 0.
2. Repeat: next = min(ugly[i2]·2, ugly[i3]·3, ugly[i5]·5); append it; advance every pointer whose candidate equals next.
3. Return the n-th entry.

Why it works

The three candidate streams are each increasing, and merging them by smallest-first produces the ugly numbers in order; advancing all matching pointers removes duplicates like 6 = 2·3 = 3·2.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Advancing only the first matching pointer emits duplicates and shifts every later answer.

Reference solution

Python

def nthUglyNumber(n: int) -> int:
    ugly = [1] * n
    i2 = i3 = i5 = 0
    for i in range(1, n):
        nxt = min(ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5)
        ugly[i] = nxt
        if nxt == ugly[i2] * 2:
            i2 += 1
        if nxt == ugly[i3] * 3:
            i3 += 1
        if nxt == ugly[i5] * 5:
            i5 += 1
    return ugly[n - 1]

Java

public static int nthUglyNumber(int n) {
    int[] ugly = new int[n];
    ugly[0] = 1;
    int i2 = 0, i3 = 0, i5 = 0;
    for (int i = 1; i < n; i++) {
        int next = Math.min(ugly[i2] * 2, Math.min(ugly[i3] * 3, ugly[i5] * 5));
        ugly[i] = next;
        if (next == ugly[i2] * 2) i2++;
        if (next == ugly[i3] * 3) i3++;
        if (next == ugly[i5] * 5) i5++;
    }
    return ugly[n - 1];
}

C++

int nthUglyNumber(int n) {
    vector<int> ugly(n, 1);
    int i2 = 0, i3 = 0, i5 = 0;
    for (int i = 1; i < n; i++) {
        int next = min(ugly[i2] * 2, min(ugly[i3] * 3, ugly[i5] * 5));
        ugly[i] = next;
        if (next == ugly[i2] * 2) i2++;
        if (next == ugly[i3] * 3) i3++;
        if (next == ugly[i5] * 5) i5++;
    }
    return ugly[n - 1];
}

JavaScript

var nthUglyNumber = function(n) {
    const ugly = new Array(n).fill(1);
    let i2 = 0, i3 = 0, i5 = 0;
    for (let i = 1; i < n; i++) {
        const next = Math.min(ugly[i2] * 2, Math.min(ugly[i3] * 3, ugly[i5] * 5));
        ugly[i] = next;
        if (next === ugly[i2] * 2) i2++;
        if (next === ugly[i3] * 3) i3++;
        if (next === ugly[i5] * 5) i5++;
    }
    return ugly[n - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium