263 Ugly Number 丑数

Description:
Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example :

Example 1:
Input: 6
Output: true
Explanation: 6 = 2 × 3

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

Example 3:
Input: 14
Output: false
Explanation: 14 is not ugly since it includes another prime factor 7.

Note:
1 is typically treated as an ugly number.
Input is within the 32-bit signed integer range: [−2^31, 2^31 − 1].

题目描述:
编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例 :

示例 1:
输入: 6
输出: true
解释: 6 = 2 × 3

示例 2:
输入: 8
输出: true
解释: 8 = 2 × 2 × 2

示例 3:
输入: 14
输出: false
解释: 14 不是丑数，因为它包含了另外一个质因数 7。

说明：
1 是丑数。
输入不会超过 32 位有符号整数的范围: [−2^31, 2^31 − 1]。

思路:

判断能否除尽 2/3/5即可
可以用迭代或者递归
时间复杂度O(lgn), 空间复杂度O(1)

代码:
C++:

class Solution 
{
public:
    bool isUgly(int num) 
    {
        if (num < 1) return false;
        if (num == 1) return true;
        if (!(num & 1)) return isUgly(num >> 1);
        if (!(num % 3)) return isUgly(num / 3);
        if (!(num % 5)) return isUgly(num / 5);
        return false;
    }
};

Java:

class Solution {
    public boolean isUgly(int num) {
        if (num < 1) {
            return false;
        }
        while ((num & 1) == 0) num >>= 1;
        while (num % 3 == 0) num /= 3;
        while (num % 5 == 0) num /= 5;
        return num == 1;
    }
}

Python:

class Solution:
    def isUgly(self, num: int) -> bool:
        if num < 1:
            return False
        if num == 1:
            return True
        while not num & 1:
            num >>= 1
        while not num % 3:
            num //= 3
        while not num % 5:
            num //= 5
        return num == 1