[Leetcode]264. 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, 5Example:
Input: n = 10 Output: 12 Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note:  
1. 1 is typically treated as an ugly number.
2. n does not exceed 1690.

Well, the most straightforward approach would be generating all ugly numbers by keeping multiplying powers of 2,3,5, and sorting them. Notably, there are 1690 ugly numbers smaller than 2^{31}-1, hence we could use that as the upper bound. More details are shown as blow credit to @StefanPochmann:

class Solution:
	# 32, 20, 14 are chosen to meet num<2^31-1
    ugly = sorted(2**a * 3**b * 5**c
                  for a in range(32) for b in range(20) for c in range(14))
    def nthUglyNumber(self, n):
        return self.ugly[n-1]

Dynamic programming

A better approach is to utilize dynamic programming. As shown below – the red numbers are part of the ugly numbers sequence – the sequence of ugly numbers is generated by keeping multiplying 2,3,5. Therefore we can maintain three-pointers with each pointing to one of 2,3,5. And we have:

next_num = min{arr[p2]*2,
				arr[p3]*3,
				arr[p5]*5}
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        # three pointers to 2,3,5
        i2=i3=i5=0
        q = [1]
        while len(q) < n:
            a,b,c = q[i2]*2, q[i3]*3, q[i5]*5
            cur = min(a,b,c)
            if cur == a:
                i2 += 1
            if cur == b:
                i3 += 1
            if cur == c:
                i5 += 1
            q.append(cur)
        return q[-1]

Reference

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments