Ugly number
Overview: The ugly number only contains prime factors2、3and5positive integer. Give you an integer n, please make a judgment nIs it an ugly number? If so, returntrue; Otherwise, returnfalse 。
Input: n = 6
Output: true
Input: n = 1
Output: true
Input: n = 14
Output: false
Method 1: Recursion + Boundary
Idea: First establish the prime factor [2,3,5] List, then loop to judge and update in turn, and finally set the boundary conditions and return.
# Recursion + Boundary
# First create a list of prime factors [2,3,5], and then loop to judge and update.
# Finally set the boundary condition and return.
class Solution:
def isUgly(self, n: int) -> bool:
if n <= 0:
return False
nums = [2, 3, 5]
for i in range(len(nums)):
while n % nums[i] == 0:
n /= nums[i]
return n == 1
Method 2: Violent recursion
Idea: Directly brutally disassemble all situations, and then update them in turn to return.
# Violent Recursion
# Directly brutally disassemble all situations, and then update them in sequence to return.
class Solution:
def isUgly(self, n: int) -> bool:
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
Summarize
If it can be removed, it will be eliminated. If it cannot be removed, it will be judged before returning.
