Skip to main content
Talentd

Ugly Number - Solution & Explanation

EasyMath11 min readAsked at: Amazon, Microsoft, Meta +5
Practice this problem

Problem Statement

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.

This C solution checks if a number is an ugly number by iteratively dividing it by the prime factors 2, 3, and 5. If n is reduced to 1, it returns true, indicating n is an ugly number.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n).
Space Complexity: O(1).

Try this approach in the editor →

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.

This C function uses recursion to repeatedly divide the number by 2, 3, or 5, checking if the reduced result is 1, confirming the number's ugliness.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n).
Space Complexity: O(log n), due to recursion stack.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoJavaScriptPHP

Python

Java

C++

Go

JavaScript

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Division Approach

Time Complexity: O(log n).
Space Complexity: O(1).

Recursive Division Approach

Time Complexity: O(log n).
Space Complexity: O(log n), due to recursion stack.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative DivisionO(log n)O(1)Best general solution. Efficient and expected in interviews.
Recursive DivisionO(log n)O(log n)Useful for demonstrating recursion and factor reduction logic.

Video Solution

Ugly Number - Leetcode 263 - Python • NeetCode • 32,622 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Ugly Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Primes

Next

Happy Number