We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Ugly Number II

Number: 264

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Microsoft, Goldman Sachs, Meta, Bloomberg, EPAM Systems

Problem Description

Given an integer n, the task is to find the nth ugly number. An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. For example, for n = 10, the sequence of ugly numbers is [1, 2, 3, 4, 5, 6, 8, 9, 10, 12], so the 10th ugly number is 12.

Key Insights

  • Ugly numbers are generated by multiplying smaller ugly numbers by 2, 3, or 5.
  • Use dynamic programming to build a sequence of ugly numbers starting from 1.
  • Maintain three pointers (for factors 2, 3, and 5) that determine the next candidate ugly number.
  • Avoid duplicate entries by checking and advancing all pointers that match the current minimum candidate.
  • The approach runs in O(n) time and uses O(n) space.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution uses a dynamic programming approach. We maintain an array (or list) that stores the ugly numbers in ascending order, starting with 1. Three pointers are used—each corresponding to the multipliers 2, 3, and 5. For each iteration:

  • Calculate the next possible ugly numbers by multiplying the number pointed to by each pointer with 2, 3, and 5.
  • Select the minimum of these candidates as the next ugly number.
  • Increment the corresponding pointer(s) to avoid duplicate calculations.
  • Continue until the nth ugly number is generated. This process ensures that each ugly number is generated in order and without duplicates.

Code Solutions

# Function to return the nth ugly number
def nthUglyNumber(n: int) -> int:
    # dp array to store ugly numbers, starting with 1 as the first ugly number
    ugly_numbers = [0] * n
    ugly_numbers[0] = 1

    # pointers for multiples of 2, 3, and 5
    i2 = i3 = i5 = 0

    # iterate to generate ugly numbers up to the nth
    for i in range(1, n):
        # Next possible ugly numbers from each prime factor
        next_multiple_of_2 = ugly_numbers[i2] * 2
        next_multiple_of_3 = ugly_numbers[i3] * 3
        next_multiple_of_5 = ugly_numbers[i5] * 5

        # Choose the smallest one as the next ugly number
        next_ugly = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5)
        ugly_numbers[i] = next_ugly

        # Move pointers if they were used
        if next_ugly == next_multiple_of_2:
            i2 += 1
        if next_ugly == next_multiple_of_3:
            i3 += 1
        if next_ugly == next_multiple_of_5:
            i5 += 1

    # The last element in the list is the nth ugly number
    return ugly_numbers[-1]

# Example usage:
print(nthUglyNumber(10))  # Output: 12
← Back to All Questions