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.

Description Solution Video 10:43

263. Ugly Number

Easy43.9% acceptance8 companies

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:

-2³¹ <= n <= 2³¹ - 1

Asked at 8 companies

GitHub

Google

TCS Zoho Amazon Microsoft Meta Bloomberg

Topics

Math

10:43

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

263. Ugly Number

Asked at 8 companies

Topics

Similar problems