Introduction
LeetCode 263: Ugly Number is a simple but interesting mathematical problem that tests your understanding of prime factorization and loop-based reduction.
An ugly number is a positive number whose prime factors only include 2, 3, or 5.
Problem Statement
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, and False otherwise.
Examples
python
Input: 6
Output: True
# 6 = 2 × 3
Input: 8
Output: True
# 8 = 2 × 2 × 2
Input: 14
Output: False
# 14 = 2 × 7 (7 is not allowed)
✅ Step-by-Step Solution in Python
Step 1: Handle Non-Positive Numbers
Ugly numbers are positive integers. So anything ≤ 0 should immediately return False.
Step 2: Repeated Division
We divide the number by 2, 3, and 5 as long as it’s divisible by those.
After removing all allowed factors (2, 3, 5), if we’re left with 1, it's an ugly number.
Python Code
python
def isUgly(n: int) -> bool:
if n <= 0:
return False
for prime in [2, 3, 5]:
while n % prime == 0:
n //= prime
return n == 1
🔍 Explanation
- Loop over [2, 3, 5]: Divide
n by each prime as long as possible.
- If after all divisions
n == 1, it had no prime factors other than 2, 3, or 5.
🧪 Dry Run Example
Input: n = 30
Process:
- 30 ÷ 2 → 15
- 15 ÷ 3 → 5
- 5 ÷ 5 → 1
Result: True
Input: n = 14
Process:
- 14 ÷ 2 → 7
- 7 is not divisible by 3 or 5 → stop
- Remaining: 7 ≠ 1 → False
⏱️ Time and Space Complexity
- Time Complexity: O(log n) – Dividing
n by 2, 3, 5 repeatedly
- Space Complexity: O(1) – No extra space used
✅ Conclusion
LeetCode 263: Ugly Number is a great warm-up for understanding:
- Prime factorization
- Loop-based simplification
- Number theory basics
Want to go deeper? Check out:
- 264. Ugly Number II – Generate the nth ugly number
- 313. Super Ugly Number – Generalized with a custom list of primes