ugly-number

Ugly Number – LeetCode 263

Problem

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. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

Answer

Original

Code

class Solution {
public:
    bool isUgly(int num) {
        if(num < 1) return false;
        num /= (((num ^ (num - 1)) + 1) >> 1);
        while(num % 3 == 0) num /= 3;
        while(num % 5 == 0) num /= 5;
        return num == 1;
    }
};

思路

简单的将2,3,5分解出来之后检查所剩是否为1，需要注意的是对于2的处理，通过位操作实现了一个时间复杂度$O(1)$的分解操作。时间复杂度$O(log{n})$，空间复杂度$O(1)$。
耗时$3$ ms，排名$78.94\%$

Better

思路

还没看到更好的解法。