LeetCode 264: Ugly Number II Solution

Master LeetCode problem 264 (Ugly Number II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

264. Ugly Number II

Medium

Hash Table Math Dynamic Programming Heap (Priority Queue)

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We will start from the first ugly number which is 1, and then iteratively generate the next ugly numbers by multiplying the existing ugly numbers (1, 2, 3, 5) by 2, 3, and 5 respectively. We will keep track of the indices for each of the factors 2, 3, and 5 to generate the next ugly number. We will select the minimum of the three possible next ugly numbers and move the corresponding index forward. This process continues until we find the nth ugly number.

Algorithm:

Initialize an array ugly to store the first n ugly numbers.
Initialize three pointers p2, p3, and p5 to track the indices of factors 2, 3, and 5 respectively.
Initialize variables next2, next3, and next5 to store the next possible ugly numbers by multiplying factors 2, 3, and 5 respectively.
Start iterating from index 1 to n-1:
- Calculate the next possible ugly numbers by multiplying the factors with the current ugly numbers at indices p2, p3, and p5.
- Select the minimum of next2, next3, and next5 as the next ugly number, and update the corresponding pointer and increment the count.
Return the last element of the ugly array.

Time Complexity: O(n) where n is the input parameter denoting the nth ugly number to be found. Space Complexity: O(n) for storing the array of n ugly numbers.

Solution Code

class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        
        for (int i = 1; i < n; i++) {
            int next2 = ugly[p2] * 2;
            int next3 = ugly[p3] * 3;
            int next5 = ugly[p5] * 5;
            
            ugly[i] = Math.min(next2, Math.min(next3, next5));
            
            if (ugly[i] == next2) p2++;
            if (ugly[i] == next3) p3++;
            if (ugly[i] == next5) p5++;
        }
        
        return ugly[n - 1];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 264 (Ugly Number II)?

This page provides optimized solutions for LeetCode problem 264 (Ugly Number II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 264 (Ugly Number II)?

The time complexity for LeetCode 264 (Ugly Number II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 264 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 264 in Java, C++, or Python.

Back to LeetCode Solutions