263. Ugly Number

1. 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.

2. Example

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.

3. Note

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

4. Solutions

Math

n = number
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution
{
public:
    // bool isUgly(int num)
    bool isUgly(int number)
    {
        if(number == 0) return false;

        while(true)
        {
            if(number == 1) return true;
            else if(number % 2 == 0) number /= 2;
            else if(number % 3 == 0) number /= 3;
            else if(number % 5 == 0) number /= 5;
            else return false;
        }
    }
};