tags: leetcode easy math

263. Ugly Number

Description

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

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.

Constraints:

• $-2^{31}$ $\leq$ n $\leq$ $2^{31}$ - 1

Code

• C

bool isUgly(int n){
    if ((n == 1) || (n == 2) || (n == 3) || (n == 5))
        return true;
    for (int i = 2;i <= ceil(sqrt(n));i ++)
        if(n%i == 0)
            return isUgly(i) & isUgly(n / i);
    
    return false;
}

• Python

from operator import truediv

def divideBy(n, div):
    while n%div == 0:
        n = n/div
        if n == 1:
            return 1
    return n

class Solution(object):
    def isUgly(self, n):
        if n <= 0:
            return False
        # tmp = divideBy(n, 2)
        # if tmp == 1:
        #     return True
        # tmp = divideBy(tmp, 3)
        # if tmp == 1:
        #     return True
        # tmp = divideBy(tmp, 5)
        # if tmp == 1:
        #     return  True
        # return False

        return divideBy(divideBy(divideBy(n, 2), 3), 5) == 1

Complexity

Space	Time
$O(1)$	$O(log(n))$

Result

C

• Runtime: 19 ms, 5.24%
• Memory usage: 5.6 MB, 26.22%

Python

• Runtime: 53 ms, 69.42%
• Memory usage: 14 MB, 12.19%