Ugly Number

Share

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return true if n is an ugly number.

Example 1
Input: 6 → Output: true (6 = 2 * 3)
Example 2
Input: 14 → Output: false (14 = 2 * 7)

Solution Approach

Divide out all factors of 2, 3, and 5. If result is 1, n is ugly.

  • If n <= 0: return false.
  • While n divisible by 2: n /= 2.
  • While n divisible by 3: n /= 3.
  • While n divisible by 5: n /= 5.
  • Return n == 1.
Java
class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;
        for (int f : new int[]{2,3,5}) while (n % f == 0) n /= f;
        return n == 1;
    }
}
  • Time Complexity: O(log N)
  • Space Complexity: O(1)