【数学, 迭代, 递归】丑数

题目

263. 丑数

---

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

给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

输入：n = 1
输出：true
解释：1 没有质因数，因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。

示例 3：

输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。

提示：

• -2^31 <= n <= 2^31 - 1

解题

方法一：数学 递归

思路

首先，根据丑数的定义，$n \le 0$ 时一定不是丑数，直接返回 false。
然后根据定义，当 $n>0$ 时如果 $n$ 是丑数，那么它一定可以写成 $n = 2^a \times 3^b \times 5^c (a\ge0,b\ge0,c\ge0)$ 的形式，而当 $a=b=c=0$ 时 $n = 1$，正是第一个丑数。

于是就可以递归求解：

• 当 n 能被 $5$ 整除时，isUgly(n) 可以转换为 isUlgy(n / 5)。
• 当 n 能被 $3$ 整除时，isUgly(n) 可以转换为 isUlgy(n / 3)。
• 当 n 能被 $2$ 整除时，isUgly(n) 可以转换为 isUlgy(n / 2)。
• 当 n 不能被 $2$、$3$、$5$ 整除时，若 $n=1$，则说明 $n$ 不包含其他质因数，是丑数；否则，说明 $n$ 包含其他质因数，不是丑数。

代码

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

方法二：数学 迭代

思路

思路与递归差不多，反复地把 $n$ 除以 $2,3,5$，直到 $n$ 不再包含质因数 $2,3,5$。若剩下的数等于 $1$，则说明 $n$ 不包含其他质因数，是丑数；否则，说明 $n$ 包含其他质因数，不是丑数。

参考：https://leetcode.cn/problems/ugly-number/solution/chou-shu-by-leetcode-solution-fazd/

代码

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