Leetcode: Ugly Number
The problem is to list numbers divisible by 2, 3 and 5 in order. Brute force approach is to just check each number for divisibility by 2, 3 and 5.
Instead of checking all the numbers we can generate the numbers that we want. Given an ugly number we can generate 3 new numbers by multiplying it with 2, 3 and 5. Suppose we start with 1
1 → [2,3 5]
use 2 as it is the minimum to generate next 3 numbers
2 → 4, 6, 10 which makes the list [3,4,5,6,10]
3 → 6, 9, 15 list →[3,4,5,6,9,10,15] and so on
Note that we are generating the same number again, 6 was inserted by 2*3 and then again by 3*2. To take care of this
- multiply numbers divisible by 5 with only 5
- multiply numbers divisible by 3 with 5 and 3
- multiply numbers divisible by 2 with 2, 3 and 5
Try generating numbers using this technique and you will understand how it works. Now since we want to keep track of the minimum number we will use a heap to store the numbers
Remarks:
- O(n) space complexity, to get the nth number we will use 3*n amount of space
- O(n * log(n)) time complexity, log(n) comes from insertion and extract-min in heap and the operation is performed 4*n times
import heapq
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
primes = [5, 3, 2]
nums = [2, 3, 5]
heapq.heapify(nums)
p = 1
for i in range(n - 1):
p = heapq.heappop(nums)
for prime in primes:
heapq.heappush(nums, p * prime)
if p % prime == 0:
break
return p