Ugly Number solution and explanation
Google
TCS
9 more videos on this problem
Ugly Number - Leetcode 263 - PythonNeetCode · 10:43 · 32K views
Ugly Number -(Amazon , Meta) : Explanation ➕ Live CodingcodestorywithMIK · 6:21 · 17K views
Ugly Number | Leetcode 263Technosage · 8:30 · 9K views
LeetCode 263 | Ugly Number | Solution Explained (Java)Xavier Elon · 3:35 · 5K views
263. Ugly Number || DSA || Leetcode Daily Challenge ||Leetcode Daily Challenge · 6:44 · 1K views
Leetcode 263. Ugly Number [Java]if else statement · 4:48 · 938 views
Can You Detect an Ugly Number? (LeetCode 263: Ugly Number)Code With Zi · 3:12 · 874 views
263 Ugly Number leetcode problem in c++ | leetcode for beginners | leetcode solutionCoding enthusiast · 4:14 · 716 views
263. Ugly Number | JavaScript | LeetCode | Daily Challenge | Detailed ExplanationLeetCodeWithMonu · 9:43 · 447 views
263. Ugly Number| Easy Level Interview Question Full Explanation in PythonEduEverybody · 3:50 · 294 views
The problem
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.
Example 1:
Input: n = 6 Output: true Explanation: 6 = 2 × 3
Example 2:
Input: n = 1 Output: true Explanation: 1 has no prime factors.
Example 3:
Input: n = 14 Output: false Explanation: 14 is not ugly since it includes the prime factor 7.
Constraints:
-231 <= n <= 231 - 1
Approach overview
Problem Overview: Determine whether an integer n is an Ugly Number. A number is considered ugly if its only prime factors are 2, 3, and 5. Negative numbers and zero are never ugly numbers.
The key observation: if you repeatedly divide a valid ugly number by 2, 3, and 5, the result eventually becomes 1. If another prime factor exists (like 7 or 11), the reduction process stops before reaching 1.
Approach 1: Iterative Division Approach (O(log n) time, O(1) space)
This approach repeatedly removes the allowed prime factors from n. Start by checking if n <= 0; such numbers cannot be ugly. Then iterate through the factors 2, 3, and 5. For each factor, divide n while it is divisible by that factor using a loop like while (n % factor == 0). After removing all occurrences of these factors, check if the remaining value equals 1. If it does, the number contained only allowed primes.
The number shrinks quickly with each division, so the loop runs at most O(log n) times. Memory usage stays constant because only a few variables are maintained. This approach relies on simple arithmetic operations from math and is the most practical implementation for production code and interviews.
Approach 2: Recursive Division Approach (O(log n) time, O(log n) space)
The recursive variant follows the same idea but expresses the factor removal using recursive calls. If n is divisible by 2, recursively check n / 2. Otherwise check divisibility by 3, then 5. When n == 1, return true. If none of the divisions apply, return false because another prime factor must exist.
Each recursive call reduces the number by one factor, so the recursion depth is bounded by O(log n). The call stack introduces O(log n) space overhead. This approach highlights clean problem decomposition and fits well when practicing recursion patterns.
Recommended for interviews: The iterative division approach is what most interviewers expect. It demonstrates recognition of the mathematical property behind ugly numbers and produces a concise O(log n) solution with constant space. Mentioning the recursive version still shows strong understanding of factor reduction and problem decomposition within math-based problems.
Approach 1: Iterative Division Approach
This approach involves dividing the number by its prime factors (2, 3, and 5) as long as it is divisible by them. If after removing all these factors, the number reduces to 1, it is an ugly number; otherwise, it is not.
def is_ugly(n: int) -> bool:
if n <= 0:
return False
for p in [2, 3, 5]:
while n % p == 0:
n //= p
return n == 1public class Solution {
public boolean isUgly(int n) {
if (n <= 0) return false;
int[] primes = {2, 3, 5};
for (int p : primes) {
while (n % p == 0) {
n /= p;
}
}
return n == 1;
}
}#include <iostream>
bool isUgly(int n) {
if (n <= 0) return false;
int primes[] = {2, 3, 5};
for (int prime : primes) {
while (n % prime == 0) {
n /= prime;
}
}
return n == 1;
}function isUgly(n) {
if (n <= 0) return false;
const primes = [2, 3, 5];
for (const p of primes) {
while (n % p === 0) {
n /= p;
}
}
return n === 1;
}#include <stdbool.h>
bool isUgly(int n) {
if (n <= 0) return false;
int primes[] = {2, 3, 5};
for (int i = 0; i < 3; i++) {
while (n % primes[i] == 0) {
n /= primes[i];
}
}
return n == 1;
}public class Solution {
public bool IsUgly(int n) {
if (n <= 0) return false;
int[] primes = {2, 3, 5};
foreach (var p in primes) {
while (n % p == 0) {
n /= p;
}
}
return n == 1;
}
}This Python solution divides the number n by 2, 3, and 5 iteratively until n reduces to 1, confirming it to be an ugly number.
Time Complexity: O(log n).
Space Complexity: O(1).
Approach 2: Recursive Division Approach
This alternative approach involves using recursion to systematically divide the number by 2, 3, and 5. By tracing back all divisions reaching 1, this method can also verify the ugliness of a number.
def is_ugly(n: int) -> bool:
def helper(num: int) -> bool:
if num == 1:
return True
if num % 2 == 0:
return helper(num // 2)
if num % 3 == 0:
return helper(num // 3)
if num % 5 == 0:
return helper(num // 5)
return False
return n > 0 and helper(n)public class Solution {
private boolean helper(int n) {
if (n == 1) return true;
if (n % 2 == 0) return helper(n / 2);
if (n % 3 == 0) return helper(n / 3);
if (n % 5 == 0) return helper(n / 5);
return false;
}
public boolean isUgly(int n) {
if (n <= 0) return false;
return helper(n);
}
}#include <iostream>
bool helper(int n) {
if (n == 1) return true;
if (n % 2 == 0) return helper(n / 2);
if (n % 3 == 0) return helper(n / 3);
if (n % 5 == 0) return helper(n / 5);
return false;
}
bool isUgly(int n) {
if (n <= 0) return false;
return helper(n);
}function isUgly(n) {
function helper(num) {
if (num === 1) return true;
if (num % 2 === 0) return helper(num / 2);
if (num % 3 === 0) return helper(num / 3);
if (num % 5 === 0) return helper(num / 5);
return false;
}
return n > 0 && helper(n);
}#include <stdbool.h>
bool helper(int n) {
if (n == 1) return true;
if (n % 2 == 0) return helper(n / 2);
if (n % 3 == 0) return helper(n / 3);
if (n % 5 == 0) return helper(n / 5);
return false;
}
bool isUgly(int n) {
if (n <= 0) return false;
return helper(n);
}public class Solution {
private bool Helper(int n) {
if (n == 1) return true;
if (n % 2 == 0) return Helper(n / 2);
if (n % 3 == 0) return Helper(n / 3);
if (n % 5 == 0) return Helper(n / 5);
return false;
}
public bool IsUgly(int n) {
if (n <= 0) return false;
return Helper(n);
}
}In this Python implementation, a nested helper function utilizes recursion to check each prime factor condition, ultimately confirming whether 1 is reached.
Time Complexity: O(log n).
Space Complexity: O(log n), due to recursion stack.
Approach 3: Default Approach
func isUgly(n int) bool {
if n < 1 {
return false
}
for _, x := range []int{2, 3, 5} {
for n%x == 0 {
n /= x
}
}
return n == 1
}class Solution {
/**
* @param Integer $n
* @return Boolean
*/
function isUgly($n) {
while ($n) {
if ($n % 2 == 0) {
$n = $n / 2;
} elseif ($n % 3 == 0) {
$n = $n / 3;
} elseif ($n % 5 == 0) {
$n = $n / 5;
} else {
break;
}
}
return $n == 1;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Division Approach | Time Complexity: O(log n). |
| Recursive Division Approach | Time Complexity: O(log n). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Division | O(log n) | O(1) | Best general solution. Efficient and expected in interviews. |
| Recursive Division | O(log n) | O(log n) | Useful for demonstrating recursion and factor reduction logic. |
Frequently asked questions
Is Ugly Number easy or hard?
Ugly Number is classified as an Easy problem on LeetCode. The difficulty lies in recognizing the mathematical property that ugly numbers contain only the prime factors 2, 3, and 5. Once that insight is clear, the implementation is straightforward.
Ugly Number Python/Java solution
Python and Java implementations both follow the same logic: repeatedly divide the number by 2, 3, and 5 while possible, then check whether the remaining value equals 1. The algorithm runs in O(log n) time with constant extra space.
How to solve Ugly Number in O(n)?
The standard solution does not require O(n) time. Using repeated division by 2, 3, and 5 reduces the number quickly, giving an O(log n) algorithm. This is more efficient than linear scanning or factorization attempts.
What is the best approach for Ugly Number?
The iterative division approach is the best solution. Repeatedly divide the number by 2, 3, and 5 while it remains divisible. If the final value becomes 1, the number contains only those prime factors. This method runs in O(log n) time and O(1) space.
Is Ugly Number asked at Google/Amazon/Meta?
Ugly Number appears frequently in coding interview preparation lists and practice sets used by companies like Amazon and Google. It tests understanding of number properties, factorization logic, and simple algorithm design.
What data structure is used in Ugly Number?
No complex data structure is required. The solution relies on arithmetic operations and loops. The problem mainly tests mathematical reasoning and factor reduction rather than arrays, stacks, or hash maps.
What is the time complexity of Ugly Number?
The optimal solution runs in O(log n) time. Each division reduces the number by at least a factor of 2, so the total number of operations grows logarithmically with respect to n. Space complexity is O(1) for the iterative approach.