Ugly Number II

Write a program to find then-th ugly number.

Ugly numbers are positive numbers whose prime factors only include2, 3, 5. For example,1, 2, 3, 4, 5, 6, 8, 9, 10, 12is the sequence of the first10ugly numbers.

Note that1is typically treated as an ugly number, andndoes not exceed 1690.

Solution

Because all ugly number are generated by a product combination of 2,3,5. We can use a generative approach to find n-th ugly number.

Use a min_heap and a set to keep track.

Starting with min_heap = [x, y,...., z], pop the minimum, x, check if x *2, x*3, x*5 exist in the set, if any of them doesn't, add those into the set, and the min_heap.

when iteration goes till i == n, the popped result from min heap is the final answer.

Time complex: O( n log n) because each heap operation push and pop cost log n, and there are n steps needed.

import heapq
class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """

        # using set, O(n)
        # each step, we use heap pop, and heap push for future elem, O(n log n)
        i = 0
        h = [1]
        inputSet = set(h)
        heapq.heapify(h)
        while i < n:
            res = heapq.heappop(h)

            if res * 2 not in inputSet:
                inputSet.add(res*2) 
                heapq.heappush(h, res * 2) # O(n log n)
            if res * 3 not in inputSet:
                inputSet.add(res*3)
                heapq.heappush(h, res * 3)
            if res * 5 not in inputSet:
                inputSet.add(res*5)
                heapq.heappush(h, res * 5)
            i += 1

        return res

Second Approach:

Time Complexity: O ( n )

Assume 3 arrays

Array 2: 1 * 2, 2* 2, 3 * 2, 4 * 2, 5* 2....

Array 3: 1 * 3, 2* 3, 3 * 3, 4 * 3, 5* 3 ...

Arrray 5: 1 * 5, 2* 5, 3 * 5, 4 * 5, 5* 5 ....

The result is essentially, merging these 3 arrays in sorted order and return the n-th element from the final array.

And because the base multiplier element is from the ugly number as well.

Thus, we use indices i2, i3, i5, to indicate where to multiply 2, 3, 5 to in the ugly number array. Find the minimum of the multiplied result, and append it to ugly array again.

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        i2, i3, i5 = 0, 0, 0
        nums = [1]
        for i in range(n):
            minVal = min(nums[i2] * 2, nums[i3] * 3, nums[i5] * 5)
            nums.append(minVal)
            if minVal == nums[i2] * 2:
                i2 += 1
            if minVal == nums[i3] * 3:
                i3 += 1
            if minVal == nums[i5] * 5:
                i5 += 1
        return nums[n-1]