Leetcode: Ugly Number

Ugly Number II | LeetCode OJ

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:

1. O(n) space complexity, to get the nth number we will use 3*n amount of space
2. 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