Ugly Number — Solution in Python, Java & C++
Ugly Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Adobe.
Ugly Number is an easy coding problem on math, asked in Amazon, Adobe and Infosys interviews.
- Difficulty: Easy
- Topics: Math
- Asked at: Amazon, Adobe, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 ugly.
Example 1
Input: n = 6
Output: true
Explanation: 6 = 2 × 3.
Example 2
Input: n = 14
Output: false
Explanation: 14 = 2 × 7, and 7 is not allowed.
Example 3
Input: n = 1
Output: true
Explanation: 1 has no prime factors at all, so the condition holds vacuously.
Constraints
-2^31 <= n <= 2^31 - 1
Hints for Ugly Number
Hint 1
Zero and negatives are never ugly.
Hint 2
Divide out every factor of 2, then every factor of 3, then every factor of 5.
Hint 3
What is left is 1 exactly when no other prime was present.
How to solve Ugly Number
Strip every factor of 2, 3 and 5 from n; what survives is 1 exactly when no other prime was involved.
Approach
- Return
falseforn <= 0. - For each
fin(2, 3, 5), dividenbyfwhile it divides evenly. - Return
n == 1.
Why it works
The prime factorisation is unique. Dividing out all the 2s, 3s and 5s leaves the product of every other prime factor with its multiplicity — an empty product (1) if and only if there were none.
Complexity
- Time —
O(log n) - Space —
O(1)
Pitfalls
0is divisible by everything and would loop forever without the guard.1is ugly by convention — it has no prime factors at all.
Reference solution
Python
def isUgly(n: int) -> bool:
if n <= 0:
return False
for f in (2, 3, 5):
while n % f == 0:
n //= f
return n == 1Java
public static boolean isUgly(int n) {
if (n <= 0) return false;
int[] factors = {2, 3, 5};
for (int f : factors) {
while (n % f == 0) n /= f;
}
return n == 1;
}C++
bool isUgly(int n) {
if (n <= 0) return false;
int factors[3] = {2, 3, 5};
for (int i = 0; i < 3; i++) {
while (n % factors[i] == 0) n /= factors[i];
}
return n == 1;
}JavaScript
var isUgly = function(n) {
if (n <= 0) return false;
const factors = [2, 3, 5];
for (let i = 0; i < factors.length; i++) {
while (n % factors[i] === 0) n /= factors[i];
}
return n === 1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.