Leetcode 263. Ugly Number(python+cpp)

题目

解法1：

最直观的解法是，一个ugly number肯定是由若干个2，3，5的乘积得到的，用一个while循环把这些能够整除的部分全部出去即可

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

解法2：recursion

class Solution:
    def isUgly(self, num: int) -> bool:
        def helper(remain):
            if remain == 1:
                return True
            flag = False
            for number in [2,3,5]:
                if remain%number == 0:
                    flag = flag or helper(remain//number)
                if flag:
                    break
            return flag
        
        if num==1 or num==0:
            return num
        return helper(num)

C++版本

class Solution {
public:
    bool isUgly(int num) {
        if (num==0 || num==1) return num;
        return helper(num);
    }
    bool helper(int remain){
        if (remain==1) return true;
        bool flag = false;
        for (auto num:{2,3,5}){
            if (remain%num==0){
                flag = flag || helper(remain/num);
            }
            if (flag) break;
        }
        return flag;
    }
};