#263

Easy

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Ugly Number

The Ugly Number problem asks you to determine if a number is divisible only by 2, 3, or 5.

Problem Statement

An ugly number is defined as a positive integer whose only prime factors are 2, 3, and 5. The task is to determine if a given integer n is an ugly number.

Given an integer n, return true if n is an ugly number, and false otherwise. For example, for n = 6, return true since 6 = 2 × 3. For n = 14, return false as 14 contains the prime factor 7.

Examples

Example 1

Input: n = 6

Output: true

6 = 2 × 3

Example 2

Input: n = 1

Output: true

1 has no prime factors.

Example 3

Input: n = 14

Output: false

14 is not ugly since it includes the prime factor 7.

Constraints

-231 <= n <= 231 - 1

Solution Approach

Prime Factorization Approach

Check if the number n can be divided by 2, 3, or 5 repeatedly until it is reduced to 1. If, at any point, the number is divisible by any prime factor other than 2, 3, or 5, return false.

Edge Case Handling

For the number n = 1, return true since 1 has no prime factors, which makes it an ugly number by definition.

Efficient Factorization

To optimize the process, keep dividing n by 2, 3, and 5 only, and exit early if n is reduced to 1. This ensures the solution runs in logarithmic time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(log n) due to repeatedly dividing n by 2, 3, and 5. Space complexity is O(1) as no extra data structures are used.

What Interviewers Usually Probe

Candidate quickly identifies the need for prime factorization.
Candidate efficiently handles edge cases like n = 1.
Candidate optimizes the solution with early termination when n is reduced.

Common Pitfalls or Variants

Common pitfalls

Failing to check edge cases like n = 1.
Mistaking non-ugly numbers with factors greater than 5 for ugly numbers.
Not reducing n completely by 2, 3, or 5 before returning true.

Follow-up variants

Implement a solution with a different time complexity for larger inputs.
Optimize using bit manipulation or other low-level techniques.
Explore the problem with larger constraints, where the approach may need to scale.

FAQ

What is an ugly number?

An ugly number is a positive integer whose only prime factors are 2, 3, and 5.

How can I check if a number is an ugly number?

You can check if a number is an ugly number by continuously dividing it by 2, 3, or 5 until it becomes 1. If any prime factor other than 2, 3, or 5 is encountered, it is not an ugly number.

What should I do for edge cases like `n = 1`?

For n = 1, return true because 1 has no prime factors, which qualifies it as an ugly number.

What is the time complexity of solving the Ugly Number problem?

The time complexity is O(log n) as the number is repeatedly divided by 2, 3, and 5.

How can GhostInterview help with this problem?

GhostInterview helps by providing a structured approach for solving the problem, optimizing the solution, and ensuring efficient handling of edge cases.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

class Solution:
    def isUgly(self, n: int) -> bool:
        if n < 1:
            return False
        for x in [2, 3, 5]:
            while n % x == 0:
                n //= x
        return n == 1

Continue Practicing

#264 ugly number ii #258 add digits #268 missing number