263. Ugly Number

Description

An ugly number is a positive integer which does not have a prime factor other than 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.

Example 3:

• Input: n = 14
• Output: false
• Explanation: 14 is not ugly since it includes the prime factor 7.

Constraints:

• -2³¹ <= n <= 2³¹ - 1

Submitted Code

class Solution(object):
    def isUgly(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 0:
            return False
        
        for p in [2, 3, 5]:
            while n % p == 0:
                n //= p
                
        return n == 1     # 마지막에 남은 숫자가 1이면 true

Runtime: 0 ms | Beats 100.00%
Memory: 12.46** MB | Beats 52.80%

필수 소수인 2, 3, 5를 리스트에 저장하는 방식을 사용했다.

Other Solutions

1st

class Solution(object):
    def isUgly(self, n):
        if n <= 0:
            return False
        
        while n % 2 == 0:
            n //= 2
        while n % 3 == 0:
            n //= 3
        while n % 5 == 0:
            n //= 5
        
        return n == 1

time complexity: 𝑂(log𝑛)
space complexity: 𝑂(1)