263. Ugly Number

  • 38.7%

https://leetcode.com/problems/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. 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.

Credits:


考虑要周全,题目要求丑数必须为正数,所以先除掉小于0的数字,不要忘了。

num%2 num&1 num/2 num>>1 除以2的时候,尽量用位运算代替,效率较高

方法一:

c / c++

1
2
3
4
for (int i=2; i<6 && num; i++)
while (num % i == 0)
num /= i;
return num == 1;

方法二:

8ms, 5.25%, May.2nd, 2016

https://leetcode.com/discuss/55542/4ms-short-c-solution

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
bool isUgly(int num) {
if(num == 1) return true;
if(num <= 0) return false;
while(num % 2 == 0) num /= 2;
while(num % 3 == 0) num /= 3;
while(num % 5 == 0) num /= 5;
return num == 1;
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
bool isUgly(int num) {
if(num<=0) return false;
while(num%2==0)
num /= 2;
while(num%3==0)
num /= 3;
while(num%5==0)
num /= 5;
return num==1;
}
};

方法三:

8ms, 5.25%, May.2nd, 2016

https://leetcode.com/discuss/52703/2-4-lines-every-language

1
2
3
4
5
6
7
8
9
class Solution {
public:
bool isUgly(int num) {
for(int i=2; i<6 && num; i++)
while(num % i == 0)
num /= i;
return num == 1;
}
};

python


https://discuss.leetcode.com/topic/27421/my-python-solution


1
2
3
4
5
6
7
8
9
10
11
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
if num <= 0:
return False
for x in [2, 3, 5]:
while num % x == 0:
num = num / x
return num == 1

Mine Solution:

64ms, 22.53%, May.2nd, 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
if num <= 0:
return False
while not (num % 2):
num = num / 2
while not (num % 3):
num = num / 3
while not (num % 5):
num = num / 5
return True if num == 1 else False

Solution 1:

68ms, 14.68%, May.2nd, 2016

https://leetcode.com/discuss/52703/2-4-lines-every-language

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
for p in 2, 3, 5:
while num % p == 0 < num:
num /= p
return num == 1

Solution 2:

68ms, 14.68%, May.2nd, 2016

https://leetcode.com/discuss/97377/python-1-line-solution

1
2
3
4
5
6
7
8
class Solution(object):
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
#n = (2**30)*(3**20)*(5**13) = 4570198050078720000000000000L
return False if num < 1 or (4570198050078720000000000000L)%num != 0 else True

Solution 3:

80ms, 4.65%, May.2nd, 2016

https://leetcode.com/discuss/64640/my-python-solution

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
if num <= 0:
return False
for x in [2, 3, 5]:
while num % x == 0:
num /= x
return num == 1

java

https://discuss.leetcode.com/topic/25616/my-2ms-java-solution

1
2
3
4
5
6
7
8
public boolean isUgly(int num) {
if(num==1) return true;
if(num==0) return false;
while(num%2==0) num=num>>1;
while(num%3==0) num=num/3;
while(num%5==0) num=num/5;
return num==1;
}

https://discuss.leetcode.com/topic/21873/simple-java-solution-with-explanation

idea:

(1) basic cases: <= 0 and == 1

(2) other cases: since the number can contain the factors of 2, 3, 5, I just remove those factors. So now, I have a number without any factors of 2, 3, 5.

(3) after the removing, the number (new number) can contain a) the factor that is prime and meanwhile it is >= 7, or b) the factor that is not the prime and the factor is not comprised of 2, 3 or 5. In both cases, it is false (not ugly number).

For example, new number can be 11, 23 –> not ugly number (case a)). new number also can be 49, 121 –> not ugly number (case b))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean isUgly(int num) {
if (num <= 0) {return false;}
if (num == 1) {return true;}
if (num % 2 == 0) {
return isUgly(num/2);
}
if (num % 3 == 0) {
return isUgly(num/3);
}
if (num % 5 == 0) {
return isUgly(num/5);
}
return false;
}

https://discuss.leetcode.com/topic/33389/java-solution-greatest-divide-by-2-3-5

clean solution to greatest divide the num using 2, 3, and 5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public static boolean isUgly(int num) {
if (num <= 0) {
return false;
}

int[] divisors = {2, 3, 5};

for(int d : divisors) {
while (num % d == 0) {
num /= d;
}
}
return num == 1;
}
}

my code:

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public boolean isUgly(int num) {
if(num<=0) return false;
while(num%2 == 0)
num /= 2;
while(num%3 == 0)
num /= 3;
while(num%5 == 0)
num /= 5;
return num==1;
}
}
谢谢你,可爱的朋友。