264. Ugly Number II

Problem Statement

link: [LeetCode.cn]https://leetcode.com/problems/ugly-number-ii/ [LeetCode]https://leetcode.cn/problems/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:

Input: n = 10 Output: 12

Input: n = 1 Output: 1

Solution Approach

Efficiently find the nth ugly number by using a heap to organize generated numbers. Starting with 1, multiply by factors 2, 3, and 5, avoiding duplicates with a set. Return the nth ugly number by popping the last element from the heap.

Algorithm

1. Utilize a set (seen) to prevent duplicates and a min heap (heap) with the initial ugly number 1.
2. Iterate n - 1 times, popping the smallest element from the heap (current ugly number).
3. For each factor in [2, 3, 5], calculate the next potential ugly number and add it to the set and heap if unseen.
4. Return the nth ugly number by popping the last element from the heap after the loop.

Implement

    class Solution:
    def nthUglyNumber(self, n: int) -> int:
      factors =[2, 3, 5]
      seen = {1}
      heap = [1]
       
      for i in range(n - 1):
          cur = heapq.heappop(heap)
          for factor in factors:
              nxt = cur * factor
              if nxt not in seen:
                  seen.add(nxt)
                  heapq.heappush(heap, nxt)
      return heapq.heappop(heap)
       

    
    

Twitter  facebook  Email