Ugly Number (LeetCode 263): Divide Out 2, 3 and 5

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.

Strip the allowed factors

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.

Edge cases

The follow-up: Ugly Number II

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.

Interview tip

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.