DevExCode

Sign in to devexcode.com with google.com

To continue, google.com will share your name, email address, and profile picture with this site. See this site's privacy policy.

264. Ugly Number II

Hash TableMathDynamic ProgrammingHeap (Priority Queue)

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:

  1. Initialize an array ugly to store the first n ugly numbers.
  2. Initialize three pointers p2, p3, and p5 to track the indices of factors 2, 3, and 5 respectively.
  3. Initialize variables next2, next3, and next5 to store the next possible ugly numbers by multiplying factors 2, 3, and 5 respectively.
  4. 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.
  5. 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.

View Leetcode Problem
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];
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question