263. Ugly Number

Time: O(log n)

Space: O(1)

Intuition

An ugly number's only prime factors are 2, 3, and 5. Repeatedly divide out all factors of 2, then 3, then 5. If the result is 1, it was an ugly number. Non-positive numbers are not ugly.

Algorithm

1If n <= 0, return false.
2For each factor in [2, 3, 5]: while n % factor == 0, n /= factor.
3Return n == 1.

Example Walkthrough

Input: n = 6

1.6 / 2 = 3. 3 / 3 = 1. Result = 1 -> ugly.

Output: true

Common Pitfalls

•n=1 is ugly (2^0*3^0*5^0). n<=0 is not ugly.

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?