Leetcode 263 ugly number

• ugly num
• 题意
• 题解
• 时间复杂度
• 代码

Leetcode 263 题

Difficulty:Easy

Tag: Math

ugly num

题意

原题目链接：https://leetcode.com/problems/ugly-number/?tab=Description

编写程序判断一个给定的数字是否为“丑陋数” ugly number

丑陋数是指只包含质因子2, 3, 5的正整数。例如，6, 8是丑陋数而14不是，因为它包含额外的质因子7 注意，数字1也被视为丑陋数

题解

将输入数重复除2, 3, 5，判断得数是否为1即可

时间复杂度

记$ num = 2^a * 3^b * 5^c * t $ ，程序执行次数为$ a + b + c $，换言之，最坏情况为$ O(log num) $

代码

python 版

class Solution:
# @param {integer} num
# @return {boolean}
def isUgly(self, num):
    if num <= 0:
        return False
    for x in [2, 3, 5]:
        while num % x == 0:
            num /= x
    return num == 1

C++版

bool isUgly(int num) {
	if(num <= 0)
    	return false;
	while(num % 2 == 0 || num % 3 == 0 || num % 5 == 0)
	{
    	if(num % 2 == 0) num /= 2;
    	if(num % 3 == 0) num /= 3;
    	if(num % 5 == 0) num /= 5;
	}
	if(num == 1)
    	return true;
	return false;
}