algoadvance

Leetcode 264. Ugly Number II

Problem Statement

Ugly numbers are positive numbers whose prime factors only include 2, 3, and 5. Given an integer n, return the n-th ugly number.

Clarifying Questions

  1. What is the range of the integer n? Typically, constraints on n would be 1 ≤ n ≤ 1690.

  2. Do we need to handle invalid input cases, such as n being non-integer or out of bounds? For this problem, we can assume input n will always be a valid integer within the given constraints.

  3. What is the expected format for the output? The output should be an integer representing the n-th ugly number.

Strategy

To solve this problem, we can use a dynamic programming (DP) approach with the following strategy:

  1. Initialization:
    • Create an array dp of size n to store the first n ugly numbers.
    • Initialize the first ugly number, dp[0], to 1.
  2. Iterative Filling:
    • Use three pointers i2, i3, and i5 to track the next multiple of 2, 3, and 5 respectively.
    • Use three variables next_2, next_3, and next_5 to store the next multiples of 2, 3, and 5 respectively initialized to 2, 3, and 5.
  3. Generate Ugly Numbers:
    • For each position i from 1 to n-1:
      • Set dp[i] to the minimum of next_2, next_3, and next_5.
      • If dp[i] is equal to next_2, increment i2 and update next_2.
      • If dp[i] is equal to next_3, increment i3 and update next_3.
      • If dp[i] is equal to next_5, increment i5 and update next_5.
  4. Return Result:
    • The n-th ugly number will be at dp[n-1].

Time Complexity

The time complexity of this approach is O(n) because we are generating each of the first n ugly numbers exactly once. The space complexity is also O(n) due to the storage required for the dp array.

Code

Here’s the Java implementation:

public class UglyNumberII {
    public int nthUglyNumber(int n) {
        if (n <= 0) return 0; // Edge case 
        int[] dp = new int[n];
        dp[0] = 1;
        int i2 = 0, i3 = 0, i5 = 0;
        int next_2 = 2, next_3 = 3, next_5 = 5;
        
        for (int i = 1; i < n; i++) {
            int next_ugly = Math.min(next_2, Math.min(next_3, next_5));
            dp[i] = next_ugly;
            
            if (next_ugly == next_2) {
                i2++;
                next_2 = dp[i2] * 2;
            }
            if (next_ugly == next_3) {
                i3++;
                next_3 = dp[i3] * 3;
            }
            if (next_ugly == next_5) {
                i5++;
                next_5 = dp[i5] * 5;
            }
        }
        
        return dp[n-1];
    }

    public static void main(String[] args) {
        UglyNumberII solution = new UglyNumberII();
        System.out.println(solution.nthUglyNumber(10)); // Output: 12
    }
}

This code follows the described strategy to generate and return the n-th ugly number efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI