How do you solve Ugly Number on LeetCode?

Ugly Number (LeetCode #263) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(1) space complexity. Key insight: An ugly number can only have 2, 3, and 5 as its prime factors.

What is the time complexity of Ugly Number?

The optimal solution for Ugly Number runs in O(log n) time and uses O(1) space. The time complexity is O(log n) because we are dividing n by 2, 3, or 5, which reduces n significantly each time.

What is the brute force solution for Ugly Number?

The brute force approach for Ugly Number is Brute Force, with O(n²) time complexity and O(1) space complexity. To determine if a number is ugly, we can repeatedly divide it by 2, 3, and 5 until it can no longer be divided. If we end up with 1, it's ugly; otherwise, it's not. The optimal Optimal Solution approach improves this to O(log n).

What algorithm or data structure is used to solve Ugly Number?

Ugly Number uses the following concepts: Math. The recommended patterns to study are: Math, Greedy.

What are the interview tips for Ugly Number?

Clarify the definition of ugly numbers before starting. Think about edge cases like 0 and negative numbers. Explain your thought process as you write code.

What are common mistakes when solving Ugly Number?

Not checking for negative numbers or zero. Confusing the definition of ugly numbers with prime numbers.

#263

Ugly Number

Easy

MathMathGreedy

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(log n)
Space	O(1)	O(1)

💡

Intuition

Time O(log n)Space O(1)

Instead of checking all numbers up to n, we can directly divide by the allowed prime factors until we either reach 1 or a number that cannot be further divided.

⚙️

Algorithm

5 steps

1Step 1: If n is less than or equal to 0, return false.
2Step 2: While n is divisible by 2, divide n by 2.
3Step 3: While n is divisible by 3, divide n by 3.
4Step 4: While n is divisible by 5, divide n by 5.
5Step 5: Return n equals 1.

solution.py7 lines

1def isUgly(n):
2    if n <= 0:
3        return False
4    for prime in [2, 3, 5]:
5        while n % prime == 0:
6            n //= prime
7    return n == 1

ℹ

Complexity note: The time complexity is O(log n) because we are dividing n by 2, 3, or 5, which reduces n significantly each time.

1An ugly number can only have 2, 3, and 5 as its prime factors.
2The number 1 is considered an ugly number since it has no prime factors.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.