LeetCode: 263 Ugly Number

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

Given an integer n, return true if n is an ugly number.

Example

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

Input: n = 8
Output: true
Explanation: 8 = 2 × 2 × 2

Input: n = 14
Output: false
Explanation: 14 is not ugly since it includes the prime factor 7.

Input: n = 1
Output: true
Explanation: 1 is considered an ugly number.

问题

丑数是指只包含质因数 2，3 和 5 的正整数。

给定一个整数 n，如果 n 是丑数，则返回 true。

例子

输入: n = 6
输出: true
解释: 6 = 2 × 3

输入: n = 8
输出: true
解释: 8 = 2 × 2 × 2

输入: n = 14
输出: false
解释: 14 不是丑数，因为它包含质因数 7。

输入: n = 1
输出: true
解释: 1 被认为是丑数。

Iterative Solution

Approach: Dividing by Prime Factors / 使用质因数不断除法

We can determine whether a number is an ugly number by repeatedly dividing it by 2, 3, and 5. If the resulting number is 1, it means all its prime factors are limited to 2, 3, and 5.

Approach Explanation / 方法解释

Check for Base Case: If n is less than or equal to 0, return false because ugly numbers are positive integers.
Repeated Division: Divide n by 2, 3, and 5 as long as it is divisible by these numbers.
Final Check: If the final result after all divisions is 1, return true. Otherwise, return false.

Iterative Algorithm / 迭代算法

If n <= 0, return false.
While n is divisible by 2, 3, or 5, divide n by these numbers.
If n == 1, return true. Otherwise, return false.

Iterative Implementation / 迭代实现

class Solution:
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False

        # Divide n by 2, 3, or 5 while it's divisible by them
        for factor in [2, 3, 5]:
            while n % factor == 0:
                n //= factor

        # If n becomes 1, it's an ugly number
        return n == 1

Iterative Solution Explanation / 迭代解决方案解释

Base Case: If n is Non-positive / 基本情况：如果 n 是非正数
```
if n <= 0:
   return False
```
- English: Ugly numbers are positive integers, so if n is less than or equal to 0, return false.
- Chinese: 丑数是正整数，因此如果 n 小于或等于 0，返回 false。
Repeated Division by 2, 3, and 5 / 不断除以 2，3 和 5
```
for factor in [2, 3, 5]:
   while n % factor == 0:
       n //= factor
```
- English: Divide n by 2, 3, and 5 while it's divisible by these factors.
- Chinese: 在 n 可以被 2，3 和 5 整除时，不断将其除以这些因数。
Final Check / 最终检查
```
return n == 1
```
- English: If n becomes 1 after all divisions, it is an ugly number. Otherwise, it's not.
- Chinese: 如果经过所有除法操作后，n 变为 1，则它是丑数。否则，不是丑数。

Recursive Solution

Approach: Recursive Dividing by Prime Factors / 使用递归进行质因数除法

We can implement the same logic recursively, dividing the number by 2, 3, and 5 in each recursive call. If n becomes 1, return true; if n becomes less than 1 or is no longer divisible by 2, 3, or 5, return false.

Recursive Algorithm / 递归算法

If n <= 0, return false.
If n == 1, return true.
If n is divisible by 2, 3, or 5, recursively divide it and call the function again.
If n is not divisible by these factors, return false.

Recursive Implementation / 递归实现

class Solution:
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False
        if n == 1:
            return True

        if n % 2 == 0:
            return self.isUgly(n // 2)
        if n % 3 == 0:
            return self.isUgly(n // 3)
        if n % 5 == 0:
            return self.isUgly(n // 5)

        return False

Recursive Solution Explanation / 递归解决方案解释

Base Case: Non-positive Number / 基本情况：非正数
```
if n <= 0:
   return False
```
- English: Return false if n is less than or equal to 0 since ugly numbers are positive.
- Chinese: 如果 n 小于或等于 0，返回 false，因为丑数是正整数。
Base Case: If n is 1 / 基本情况：如果 n 是 1
```
if n == 1:
   return True
```
- English: If n becomes 1, return true since it’s considered an ugly number.
- Chinese: 如果 n 变为 1，返回 true，因为它被认为是丑数。
Recursive Calls / 递归调用
```
if n % 2 == 0:
   return self.isUgly(n // 2)
if n % 3 == 0:
   return self.isUgly(n // 3)
if n % 5 == 0:
   return self.isUgly(n // 5)
```
- English: If n is divisible by 2, 3, or 5, recursively divide it and call the function again.
- Chinese: 如果 n 可以被 2，3 或 5 整除，递归地将其除以相应的因数并再次调用函数。
Return False if Not Divisible / 如果无法整除返回 False
```
return False
```
- English: If n is not divisible by 2, 3, or 5, return false as it's not an ugly number.
- Chinese: 如果 n 不能被 2，3 或 5 整除，返回 false，因为它不是丑数。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(log n), where n is the given number. We keep dividing n by 2, 3, or 5 until it becomes 1.
Space Complexity / 空间复杂度:
- Iterative Solution: O(1), since we are not using any additional space.
- Recursive Solution: O(log n), due to the recursive call stack.

Key Concept / 关键概念

Dividing by Prime Factors / 质因数除法: By repeatedly dividing a number by 2, 3, and 5, we ensure that its only prime factors are 2, 3, or 5. If it reduces to 1, it’s an ugly number.
Recursion / 递归: The recursive solution uses the same concept, breaking the problem down by dividing n in each recursive call.

Summary / 总结

English: We can solve the problem of determining whether a number is ugly by dividing it by `2

, 3, and 5 until it becomes 1`. Both iterative and recursive solutions achieve the same result.

Chinese: 我们可以通过将数字不断除以 2，3 和 5 来解决是否为丑数的问题，直到它变为 1。迭代和递归解决方案都能实现相同的结果。

Tips / 提示

English: Ensure to check for non-positive numbers first, as ugly numbers are always positive.
Chinese: 确保首先检查非正数，因为丑数总是正数。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice number theory problems involving divisibility and prime factorization to deepen your understanding of number manipulation.
Chinese: 练习涉及可整除性和质因数分解的数论问题，以加深对数字操作的理解。

Ugly Number - Leetcode 263 - Python by NeetCode

Post Views: 6

CODEBITWAVE