263. Ugly Number

Leetcode Math

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.

Example 1:

Input: 6
Output: true
Explanation: 6 = 2 × 3

Example 2:

Input: 8
Output: true
Explanation: 8 = 2 × 2 × 2

Example 3:

Input: 14
Output: false 
Explanation: 14 is not ugly since it includes another prime factor 7.

Note:

• 1 is typically treated as an ugly number.
• Input is within the 32-bit signed integer range: [−$2^{31}$, $2^{31}$ − 1].

分析

这道题目如果直接按照题目的描述来解决：$n$试着处以任何一个小于$n$的整数，结果只有2,3,5可以整除的$n$是ugly number。这很显然不行，因为当$n$很大的时候，这个循环得多大啊。

利用逆向思维，既然只能被2,3,5整除，那就整除这些数字，看最后结果是不是1。

public boolean isUgly(int num) {
    // 负数不是ugly number
    if (num <= 0) return false;
    // 如果能被2,3,5整除，就整除
    while(num % 2 == 0) num /= 2;
    while(num % 3 == 0) num /= 3;
    while(num % 5 == 0) num /= 5 ;
    return num == 1;
}