263. Ugly Number

EasyView on LeetCode

Math

Time: O(log n)

Space: O(1)

Problem Overview

An ugly number has no prime factors other than 2, 3, and 5.

Intuition

An ugly number has no prime factors other than 2, 3, and 5. Divide n by each of those primes repeatedly until it no longer divides evenly. If what remains is 1, n was ugly; any other remainder (e.g. 7) means a forbidden prime factor. Non-positive n is not ugly.

Algorithm

1If n <= 0, return false.
2For each prime in [2, 3, 5]: while n % prime == 0, set n = n / prime.
3After all three loops, return true iff n == 1.

Example Walkthrough

Input: n = 14

1.14 / 2 = 7. No further division by 2, 3, or 5.
2.Remaining 7 ≠ 1 → 14 has prime factor 7.

Output: false

Common Pitfalls

•n = 1 is ugly (empty product of 2, 3, 5).
•n <= 0 is not ugly.
•Check factors in any order; division order does not matter.

263.cs

// Approach: Repeatedly divide by 2, 3, and 5; the number is ugly
// if and only if the final result equals 1.
// Time: O(log n) Space: O(1)

public class Solution
{
    public bool IsUgly(int n)
    {
        if (n == 0)
            return false;

        foreach (int prime in new int[] { 2, 3, 5 })
        {
            while (n % prime == 0)
                n /= prime;
        }

        return n == 1;
    }
}

Was this solution helpful?