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:
n = 6
, the function should return true
because 6 = 2 * 3
.n = 1
, the function should return true
because 1 has no prime factors other than those allowed.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
.
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.
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):
n
, and the inner loop (prime check) goes up to the square root of i
in the worst case.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:
n
is less than or equal to 0, it's not an ugly number.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):
n
by 2, 3, and 5, effectively reducing n
exponentially. The number of divisions is logarithmic with respect to n
.