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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Ugly Number II

Difficulty: Medium

Problem Description

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.

Key Insights

  • Ugly numbers are generated by multiplying the previous ugly numbers by 2, 3, or 5.
  • The smallest ugly number is 1, which is considered an ugly number by definition.
  • We can maintain a list of ugly numbers and use a min-heap (priority queue) to efficiently find the next ugly number.
  • Each time we extract the smallest ugly number from the heap, we can generate new ugly numbers by multiplying it by 2, 3, and 5.

Space and Time Complexity

Time Complexity: O(n log n) - due to the heap operations for generating ugly numbers. Space Complexity: O(n) - for storing the list of ugly numbers.

Solution

To solve the problem, we use a min-heap to keep track of the next potential ugly numbers. We start with the first ugly number (1) in the heap. In each iteration, we extract the smallest number from the heap, and then generate new numbers by multiplying this number by 2, 3, and 5. We also ensure that we do not add duplicate numbers to the heap.

Code Solutions

import heapq

def nthUglyNumber(n):
    ugly_numbers = [1]  # Initial ugly number
    heap = []
    heapq.heappush(heap, 1)
    seen = {1}

    for _ in range(n):
        current_ugly = heapq.heappop(heap)

        # Generate new ugly numbers
        for factor in [2, 3, 5]:
            new_ugly = current_ugly * factor
            if new_ugly not in seen:
                seen.add(new_ugly)
                heapq.heappush(heap, new_ugly)

    return current_ugly
← Back to All Questions