Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
v3: Dynamic Programming, more memory-friendly for large numbers solution in Speedy category for Ugly Numbers by Phil15
def ugly_number(n: int) -> int:
# I did "ugly = [1] + [0] * (n - 1)" before, but I had memory error on very
# large numbers. I did "ugly = deque([1])", append numbers and popleft when
# content was not needed anymore, managing indexes was more complex, it
# worked fine but deque was not efficient enough in my opinion.
# A dict is way more efficient here, and managing indexes remains easy.
ugly = {1: 1}
# Indexes of the number that will be used for the next multiple of 2, 3, 5.
i = i2 = i3 = i5 = 1 # i == min(i2, i3, i5)
# Next multiples of 2, 3, 5.
m2, m3, m5 = 2, 3, 5
# To know if ugly as a dict is efficient or not.
# max_length = length = 1 # len(ugly)
for idx in range(2, n + 1):
# Choose the minimal multiple.
# Like before, I don't use "min" because it's a bit faster without.
u = (m2 if m2 <= m3 else m3) if m3 <= m5 else (m2 if m2 <= m5 else m5)
ugly[idx] = u
# length += 1
# if length > max_length:
# max_length = length
# Update indexes/multiples.
if u == m2:
i2 += 1
m2 = ugly[i2] * 2
if u == m3:
i3 += 1
m3 = ugly[i3] * 3
if u == m5:
i5 += 1
m5 = ugly[i5] * 5
if i < i2 and i < i3 and i < i5:
del ugly[i]
# length -= 1
i += 1
# print('For n={: <10} max_length={: <7} ({:.3g}% of n)'
# .format(n, max_length, max_length / n * 100))
# For n=4 max_length=4 (100% of n)
# For n=100 max_length=45 (45% of n)
# For n=1500 max_length=303 (20.2% of n)
# For n=1000000 max_length=24625 (2.46% of n)
# For n=1000000000 max_length=2480873 (0.248% of n)
# "max_length" is still increasing with n but much less rapidly than n.
return ugly[n]
"""
ugly_number(10**9) == 6216075755565244861630816332872072003947056519089652706591632409642337022002753141824417540777256732780370172616615291935540418620025524916729500086831454711313694078635504004160312872951788703647948382456091072701600790562071797590306654765882256990391763887850141154482249915927439184562828227449023750262318234797192076792208033475638322151983772515798004125909334741121595323950448656375104457026997424772966917441779406172736975588556800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
On my computer, it took 26 minutes 36 seconds and the python process took up to 1.3 Gb of memory.
"""
Dec. 9, 2021
Comments: