Ugly Number Problems on LeetCode
The problems on leetcode are listed below, and the number of stars indicate the difficulty of each problem.
Definition and Analysis
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5 . However, sometimes this definition can be extended to a list of prime factors pl, such as [3, 5, 7], [2, 3, 7, 11]. This means an ugly number can be represented as:
u=(2^i)*(3^j)*(5^k)
There are different types of questions involved with ugly number:
- Check if a number is an ugly number.
- Find the n-th ugly number.
Checking
The first question is easy, to check if a number u, we start from u, keep divide it by any of the prime factors that is divisible until the number u=1 .
n-th Ugly Number
To find the n-th ugly number, there are multiple ways to do it.
Method 1: First and the most naive solution is for each prime factor, get n top ugly number for each prime factor, and merge them in a set, sort the list and the n-th ugly number will be the n-th number in the list. The complexity will be O(nlgn) and space complexity is O(n). For example:
n=4
2: [2, 4, 6, 8]
3: [3, 6, 9, 12]
5: [5, 10, 15, 20]
list = [2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 20]
4th will be 5Method 2: The second will be more efficient. For each prime factor, we list its current smallest number, at first it will be [2, 3, 5]. Then, we choose the smallest which is 2 from the list, and we put 2*2 inside, the candidates list become [3, 4, 5]. Then we pop 3 out, and supply the candidates with 6, [4, 5, 6].
n=4, candidates = [2, 3, 5]
1-th: 2, put 2+2 inside, candidates =[3, 4, 5]
2-th: 3, put 3+3 inside, candidates=[4,5,6]
3-th: 4, put 4+2 inside, candidates =[5, 6, 6],
4-th: 5, put 5+5 inside, candidates = [6, 6, 10]
5-th: 6, however, there are two situations that both equals to 6, put 6+2 inside, and 6+3, inside, candidates = [8, 9, 10]
6-th: 8, put 8+2 inside, candidates = [9, 10, 10]
7-th: 10, put 10+2, 10+5 inside, candidates = [9, 12, 15]Imagine the candidates list as a buffer, once we take one, we supply each prime factor’s next number to the list. This only require constant number of space, and the time complexity will be O(n). However, when n is extremely large, this is still not doable as shown in 1201. Ugly Number III(**).
Method 3: What if the first prime factor is so small, and the other prime factors are so large, and that most of the time that we only need to apply the first prime factor. Another approach is we first only use the first smallest prime factor, we build a list of n candidates here:
n = 6,
candidates = [2, 4, 6, 8, 10, 12].
The maximum is 12.
Now, we check prime factor 3,
3 < 12, and 3 not in candidates, use 3 to replace 12. max_2 = 10, max_3 = 3
3+3 < 10, and 6 is overlap with previous number, skip.
3+3+3 = 9 < 10, use 9 to replace 10, max_2= 8, max_3=9. We need to pay attention, when we are decreasing the maximum one, it might be equal to the other maximum for each factor, then in this case, we have to decrease the other maximum to make sure `max_2 > max_3 > max_5`. The time complexity in this case is O(p1*n//p2+p1*n//p2). When p2 and p3 is a lot larger, this will greatly decrease the time complexity.
Problems
263. Ugly Number
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. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.
Note:
1is typically treated as an ugly number.- Input is within the 32-bit signed integer range.
Solution: num =2^i3^j5^k, keep divide [2,3,5], if the remainder is==0, or else stop. return False
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
if num==0:
return False
factor =[2,3,5]
for f in factor:
while num%f==0:
num/=f
return num==1264. Ugly Number II
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number, and n does not exceed 1690.
Two solutions: 1. use a list to save all the first 1690 numbers and sort the list. 2. to generate in time, use three pointers, to record the last result to use each pointer.
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
# nums=[]
# for i in range(int(log(1690,5))):
# for j in range(int(log(1690,3))):
# for k in range(int(log(1690,2))):
# nums.append((5**i)*(3**j)*(2**k))
# nums.sort()
# print(len(nums))
# print(nums)
nums=[1]
idx_2, idx_3, idx_5 = 0, 0, 0
for i in range(n-1):
next2=nums[idx_2]*2
next3=nums[idx_3]*3
next5=nums[idx_5]*5
next=min(next2,next3,next5)
nums.append(next)
if next==next2:
idx_2+=1
if next ==next3:
idx_3+=1
if next==next5:
idx_5+=1
return nums[-1]313. Super Ugly Number
Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
Solution:the same as the last, except that the primes different
def nthSuperUglyNumber(self, n, primes):
"""
:type n: int
:type primes: List[int]
:rtype: int
"""
nums=[1]
idexs=[0]*len(primes) #first is the current idex
for i in range(n-1):
min_v = maxsize
min_j = []
for j, idex in enumerate(idexs):
v = nums[idex]*primes[j]
if v<min_v:
min_v = v
min_j=[j]
elif v==min_v:
min_j.append(j) #we can get mutiple j if there is a tie
nums.append(min_v)
for j in min_j:
idexs[j]+=1
return nums[-1]1201. Ugly Number III
Write a program to find the n-th ugly number.
Ugly numbers are positive integers which are divisible by a or b or c.
Example 1:
Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.Example 2:
Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.Example 3:
Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.Example 4:
Input: n = 1000000000, a = 2, b = 217983653, c = 336916467
Output: 1999999984Use method 3:
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
t = sorted(list(set([a, b, c])))
e = t[0]*n
t_max = [e]+[-float('inf')]*(len(t)-1) # max for each prime factor
max_index = 0
ans = max(t_max)
for j, v in enumerate(t[1::]): # for the next prime factor, replace its number.
i = 1
while True:
temp = i * v # possible ugly number within the range of n.
if temp >= t_max[max_index]:
break
if any([temp%d==0 for d in t[:j+1]]): #exist
i+= 1
continue
else: # not exist, kick out max
temp_max = t_max[max_index] - t[max_index]
t_max[max_index] = temp_max
#check if there are other that equals to the max
for k in range(max_index+1, j+1):
if t_max[k] == temp_max:
t_max[k] -= t[k]
t_max[j+1] = max(t_max[j+1], temp) #update current max
max_index = t_max.index(max(t_max))
i+=1return max(t_max)
