Taro Logo

Ugly Number

Easy
Apple logo
Apple

An ugly number is a positive integer which does not have a prime factor other than 2, 3, and 5. Given an integer n, return true if n is an ugly number.

Here are a few examples:

  1. If n = 6, the function should return true because 6 = 2 * 3.
  2. If n = 1, the function should return true because 1 has no prime factors other than those allowed.
  3. If n = 14, the function should return false because 14 = 2 * 7, which includes the prime factor 7 which is not allowed.

Write a function to determine if a given number n is an ugly number, considering the constraints: -2^31 <= n <= 2^31 - 1.

Solution


Ugly Number Problem

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

Naive Approach

The brute force approach involves checking if n is divisible by any prime number other than 2, 3, and 5. We iterate through possible prime factors and if we encounter any other than 2, 3, 5 then we know that the number is not an ugly number.

Code (Python):

def is_ugly_naive(n):
    if n <= 0:
        return False
    if n == 1: return True

    for i in range(2, n + 1):
        if n % i == 0:
            is_prime = True
            for j in range(2, int(i**0.5) + 1):
                if i % j == 0:
                    is_prime = False
                    break
            if is_prime:
                if i not in [2, 3, 5]:
                    return False
    return True

Big O Analysis (Naive Approach):

  • Time Complexity: O(n * sqrt(n)). The outer loop goes up to n, and the inner loop (prime check) goes up to the square root of i in the worst case.
  • Space Complexity: O(1). Constant extra space.

Optimal Approach

The optimal approach is based on repeatedly dividing the given number n by the prime factors 2, 3, and 5 until it is no longer divisible by any of them. If the remaining number is 1, then the original number n is an ugly number.

Edge Cases:

  • If n is less than or equal to 0, it's not an ugly number.
  • If n is 1, it's considered an ugly number.

Code (Python):

def is_ugly(n):
    if n <= 0:
        return False
    
    for p in [2, 3, 5]:
        while n % p == 0:
            n //= p
            
    return n == 1

Big O Analysis (Optimal Approach):

  • Time Complexity: O(log n). The while loops divide n by 2, 3, and 5, effectively reducing n exponentially. The number of divisions is logarithmic with respect to n.
  • Space Complexity: O(1). Constant extra space.