Ugly Number

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.