264. Ugly Number II

[mah-shamim]

Topics: Hash Table, Math, Dynamic Programming, Heap (Priority Queue)

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

Example 1:

• Input: n = 10
• Output: 12
• Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

Example 2:

• Input: n = 1
• Output: 1
• Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Constraints:

• 1 <= n <= 1690

Hint:

1. The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
3. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L₁, L₂, and L₃.
4. Assume you have U_k, the k^th ugly number. Then U_k+1 must be Min(L₁ * 2, L₂ * 3, L₃ * 5).

[topugit]

We can use a dynamic programming approach. We'll maintain an array to store the ugly numbers and use three pointers to multiply by 2, 3, and 5.

Let's implement this solution in PHP: 264. Ugly Number II

<?php
function nthUglyNumber($n) {
    $uglyNumbers = array_fill(0, $n, 0);
    $uglyNumbers[0] = 1;
    
    $i2 = $i3 = $i5 = 0;
    $next2 = 2;
    $next3 = 3;
    $next5 = 5;

    for ($i = 1; $i < $n; $i++) {
        $nextUgly = min($next2, $next3, $next5);
        $uglyNumbers[$i] = $nextUgly;

        if ($nextUgly == $next2) {
            $i2++;
            $next2 = $uglyNumbers[$i2] * 2;
        }
        if ($nextUgly == $next3) {
            $i3++;
            $next3 = $uglyNumbers[$i3] * 3;
        }
        if ($nextUgly == $next5) {
            $i5++;
            $next5 = $uglyNumbers[$i5] * 5;
        }
    }

    return $uglyNumbers[$n - 1];
}

// Example usage:
$n1 = 10;
echo nthUglyNumber($n1);  // Output: 12
$n2 = 1;
echo nthUglyNumber($n2);  // Output: 1
?>

Explanation:

• Dynamic Programming Array: We maintain an array uglyNumbers where each element corresponds to the next ugly number in the sequence.
• Pointers (i2, i3, i5): These pointers track the current position in the sequence for multiplying by 2, 3, and 5, respectively.
• Next Multiples (next2, next3, next5): These variables hold the next potential multiples of 2, 3, and 5.
• Main Loop: We iterate from 1 to n-1, and in each iteration, we determine the next ugly number by taking the minimum of next2, next3, and next5. Depending on which value is the minimum, we update the corresponding pointer and calculate the next multiple.
• Return: Finally, we return the nth ugly number.

This solution ensures that we generate the sequence of ugly numbers efficiently, focusing only on valid ugly numbers and skipping non-ugly numbers.

[mah-shamim]

Thanks to solve the "Ugly Number II" problem efficiently