AlgoMaster Logo

Ugly Number

Last Updated: March 28, 2026

easy

Understanding the Problem

We need to determine whether a given integer is an "ugly number." The definition is simple: a positive integer whose only prime factors are 2, 3, and 5. So numbers like 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 are all ugly, while 7, 11, 13, 14 are not.

There are a couple of things to watch out for. First, the number must be positive. Zero and negative numbers are never ugly. Second, 1 is considered ugly because it has no prime factors at all, which trivially satisfies the condition. Third, we're not just checking if 2, 3, or 5 divides the number. We need to verify that after removing all factors of 2, 3, and 5, nothing remains (i.e., the number reduces to 1).

The key observation is this: if we keep dividing n by 2, 3, and 5 as long as it's divisible, we should end up with 1. If we end up with anything else, the number has a prime factor other than 2, 3, or 5, and it's not ugly.

Key Constraints:

  • -2^31 <= n <= 2^31 - 1 → The input spans the full 32-bit integer range. We need to handle negative numbers, zero, and very large positive numbers. Since each division reduces n by at least half, the maximum number of divisions is O(log n), which is at most 31 for a 32-bit integer.

Approach 1: Trial Division (Iterative)

Intuition

The most natural way to check if a number is ugly: just keep dividing out the allowed prime factors and see what's left. If n is divisible by 2, divide by 2. Keep going until it's not divisible by 2 anymore. Then do the same for 3, and then for 5. If the number reduces to 1, every prime factor was 2, 3, or 5. If it doesn't reduce to 1, something else is lurking in the factorization.

Before we start dividing, we handle the edge case: if n is zero or negative, return false immediately. These can never be ugly.

Algorithm

  1. If n <= 0, return false.
  2. While n is divisible by 2, divide n by 2.
  3. While n is divisible by 3, divide n by 3.
  4. While n is divisible by 5, divide n by 5.
  5. Return true if n == 1, otherwise false.

Example Walkthrough

1Start: n = 12
12
1/6

Code

This approach works perfectly, but writing three separate while loops feels repetitive. Can we combine them into a single loop over the allowed factors?

Approach 2: Factor Loop (Cleaner Variant)

Intuition

Approach 1 works perfectly, but we can clean it up by storing the allowed factors in a list and iterating over them. This doesn't change the time or space complexity, but it makes the code more extensible. If the problem changed to allow prime factors {2, 3, 5, 7}, we'd just add 7 to the list instead of writing a fourth while loop.

Algorithm

  1. If n <= 0, return false.
  2. For each factor in [2, 3, 5]:
    • While n is divisible by that factor, divide n by it.
  3. Return true if n == 1, otherwise false.

Example Walkthrough

1Start: n = 30
30
1/7

Code