---
# System prepended metadata

title: Leetcode 263. Ugly Number
tags: [Math]

---

###### tags: `Math`
# Leetcode 263. Ugly Number

1. 問題描述
    An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

    Given an integer n, return true if n is an ugly number.

    Example 1:
    
        Input: n = 6
        Output: true
        Explanation: 6 = 2 × 3
    
    Example 2:

        Input: n = 1
        Output: true
        Explanation: 1 has no prime factors, therefore all of its prime factors 
        are limited to 2, 3, and 5.
    
    Example 3:
    
        Input: n = 14
        Output: false
        Explanation: 14 is not ugly since it includes the prime factor 7.
    
2. Input的限制
    * -2^31^ <= n <= 2^31^ - 1.
        
3. 思考流程
    * Maths
    此題定義了，一個數若只擁有 2, 3, 5 為質因數，就是所謂的 ugly number。因此，我們依照定義和題目給的限制，如果是負數的話，則此數不是 ugly number。如果是正數，則我們將此數一直除 2，直到產生餘數為止，接著依序對 3 和 5 做一樣的除法程序，最後剩下來的數如果不等於 1，則此數不是ugly number。<br>

        因為主要的迴圈在除 2, 3, 5 上，一個數 N 如果最多能被 2 除 k 次，則 2^k^ <= N。取 log 後，k <= log~2~N，故 time complexity 是 O(logN)。而 space complexity 是 O(1)。

        Time Complexity: O(logN); Space Complexity: O(1)
4. 測試
    * test 1
    Input: n = -3
    Output: false
    * test 2
    Input: n = 30
    Output: true
    * test 3
    Input: n = 42
    Output: false