An ugly number is a positive integer whose only prime factors are 2, 3 and 5. Given n, return whether it's ugly. 6 is ugly, 14 is not (it has a factor of 7), and 1 counts as ugly by convention.
Divide n by 2, 3 and 5 as long as it's divisible. If what's left is 1, nothing else was hiding in there.
def is_ugly(n: int) -> bool:
if n <= 0:
return False
for p in (2, 3, 5):
while n % p == 0:
n //= p
return n == 1
Each division at least halves n, so the loop runs O(log n) times.
n <= 0 is never ugly; without that guard, 0 % 2 == 0 loops forever.n == 1 returns True immediately.If asked for the nth ugly number, switch to three pointers merging the sequences 2x, 3x and 5x. Mentioning that you know the follow-up exists is a nice signal.
Call out the zero guard before you code it. Practising that habit of naming edge cases first is easier with a tool like Linkjob AI's coding interview copilot.
Disclosure: I work on Linkjob AI.