264. Ugly Number II

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

Approach 01:

#include <vector>
#include <algorithm>

class Solution {
public:
    int nthUglyNumber(int n) {
        std::vector<int> uglyNumbers{1};  // Vector to store ugly numbers
        int index2 = 0;  // Pointer for multiples of 2
        int index3 = 0;  // Pointer for multiples of 3
        int index5 = 0;  // Pointer for multiples of 5

        while (uglyNumbers.size() < n) {
            const int nextMultipleOf2 = uglyNumbers[index2] * 2;
            const int nextMultipleOf3 = uglyNumbers[index3] * 3;
            const int nextMultipleOf5 = uglyNumbers[index5] * 5;
            const int nextUglyNumber = std::min({nextMultipleOf2, nextMultipleOf3, nextMultipleOf5});
            
            if (nextUglyNumber == nextMultipleOf2)
                ++index2;
            if (nextUglyNumber == nextMultipleOf3)
                ++index3;
            if (nextUglyNumber == nextMultipleOf5)
                ++index5;
                
            uglyNumbers.push_back(nextUglyNumber);
        }

        return uglyNumbers.back();  // Return the nth ugly number
    }
};

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        uglyNumbers = [1]  # List to store ugly numbers
        index2 = 0  # Pointer for multiples of 2
        index3 = 0  # Pointer for multiples of 3
        index5 = 0  # Pointer for multiples of 5

        while len(uglyNumbers) < n:
            nextMultipleOf2 = uglyNumbers[index2] * 2
            nextMultipleOf3 = uglyNumbers[index3] * 3
            nextMultipleOf5 = uglyNumbers[index5] * 5
            nextUglyNumber = min(nextMultipleOf2, nextMultipleOf3, nextMultipleOf5)
            
            if nextUglyNumber == nextMultipleOf2:
                index2 += 1
            if nextUglyNumber == nextMultipleOf3:
                index3 += 1
            if nextUglyNumber == nextMultipleOf5:
                index5 += 1
                
            uglyNumbers.append(nextUglyNumber)

        return uglyNumbers[-1]  # Return the nth ugly number

Time Complexity

• Calculating Next Ugly Numbers:

  The algorithm iteratively calculates the next ugly number by finding the minimum of the next multiples of 2, 3, and 5. This operation is performed \( n \) times, where \( n \) is the input parameter. Each iteration involves a constant amount of work, making this step \( O(n) \).

• Overall Time Complexity:

  The overall time complexity of the algorithm is \( O(n) \).

Space Complexity

• Storage of Ugly Numbers:

  The space required to store the ugly numbers is \( O(n) \), as the algorithm maintains a list of all ugly numbers up to the \( n \)th one.

• Pointer Variables:

  The additional space used by the pointer variables (index2, index3, and index5) is constant, \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(n) \) due to the storage required for the list of ugly numbers.