Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
heapq solution in Clear category for Ugly Numbers by HeNeArKr
# Algorithm adapted from
# https://www.geeksforgeeks.org/ugly-numbers/
# Pretty sure I would not have been able to come up with the basic idea
# on my own.
# Build ugly number sequence from 3 subsequences based on 2, 3, and 5.
# Build up all sequences simultaneously, but "later" elements of
# subsequences are determined by "earlier" elements of the
# ugly numbers sequence.
# Next element of ugly numbers sequence is the minimum of the elements
# of the subsequences. Use priority queue to always pull the minimum
# available.
import heapq
def ugly_number(n: int) -> int:
hp = [1]
heapq.heapify(hp)
prev = 0
for _ in range(n):
while (m := heapq.heappop(hp)) == prev: # assignment expression
continue
for num in (2, 3, 5):
heapq.heappush(hp, m * num)
prev = m
return m
Dec. 12, 2021
Comments: