Ugly number, Not that Ugly to be honest!

Question

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.

Leetcode

Disclaimer: This question not only helps you understand heaps, but also primes and some of their characteristics, necessary for solving interview problems.

Refraiming the problem

1. What are primes and what is the The fundamental theorem of arithmetic?

“The fundamental theorem of arithmetic (FTA), also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer greater than 1 either is prime itself or is the product of a unique combination of prime numbers”

2. Put Simply: You can make any whole number with a set of prime numbers. And for each of those whole numbers there will be only one set of prime to do the job. Keep these points in mind when using prime factorization:
• You can use the same prime multiple times.
• The order of primes used does not affect the result.
1. Compose = 2*3*3 = 18 or 3*2*3 = (also)18
2. Decompose = 18 /2 —> 9 /3 —> 3/3 —> 1


Courtesy : Bubbly Prime

For more information, check out this great article.

3. Before we move on… let's also clear the air on primes. Primes are numbers only divisible by themselves (and 1, since all numbers are divisible by 1). If a number contains a prime other than 2, 3, or 5, we can be sure that when we decompose it, we will have to divide it by that prime at some point in order to reach one. To check if a number is ugly, we will only divide the number by 2, 3, and 5. If there are any other primes left, they will be singled out in the end(or a combination of them), since primes can only be divided by themselves. For example, 7 and 13 are both primes. When we multiply them to get 91, it cannot be divided by either 2, 3, or 5. This is because 91 is a unique combination of prime factors, but it is not considered an "ugly" number because it has more prime factors than just 2, 3, and 5.
4. To determine if a number is ugly, it must be divisible by either 2, 3, and 5 at every step of the decomposition process. This is a question on its own and can be found on LeetCode.
1. Code
Copy

class Solution:
    def isUgly(self,n):
        if n <= 0:
            return False
        
        while n > 1:
        
            if n % 2 == 0:
                n = n // 2
            elif n % 3 == 0:
                n = n // 3
            elif n % 5 == 0:
                n = n // 5
            else: # at any point not divisable by 2 3 or 5
                break
        return n == 1

Building the ugly number from bottom up

1. We can brute force it by checking every number from 1 until we reach n and simply return that, this will however give us a time limit exceeded error. As we are generating many numbers and checking them, that is extra work. Is there a way to only create ugly numbers?
Copy

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        i = 1
        count = 1

        while n > count:
            i += 1
            if self.isUgly(i):
                count += 1

        return i

		 def isUgly(self,n):
        if n <= 0:
            return False
        
        while n > 1:
        
            if n % 2 == 0:
                n = n // 2
            elif n % 3 == 0:
                n = n // 3
            elif n % 5 == 0:
                n = n // 5
            else: # at any point not divisable by 2 3 or 5
                break
        return n == 1

2. Understanding the ugliness of the number is important to build upon that logic. Instead of breaking down the number, we construct it from the beginning. So all the numbers we have are ugly.
3. We know one thing before we start: 1 is a factor of every number, and every number is a factor of itself. Additionally, the example provides us with the sequence of the first 10 ugly numbers: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12. We can be sure 1 is the first ugly number.
4. We can start with 1 and multiplied it by 2, 3, and 5 to create the next set of ugly numbers.
1. 1 * 2 = 2
2. 1 * 3 = 3
3. 1 * 5 = 5
5. The next three ugly numbers are 2, 3, and 5. They are all factors of the prime numbers 2, 3, and 5 and can be divided by any combination of these three primes Hence they are ugly. We can store them in a list.
6. After the first iteration, we have four ugly numbers: 1, 2, 3, 5. To further compose ugly numbers, we take the existing numbers (1, 2, 3, 5) starting with the smallest and multiply them by 2, 3, and 5. We can be certain that since these numbers are composed of only these three prime factors, they are definitely ugly. For example, multiplying the existing numbers by 2 yields 2, 4, 6, 10 which are also ugly.
1. have = [1, 2, 3, 5] created(new) = [2, 4, 6, 10]
7. The duplicate conundrum.
1. There was an issue with the previous solution. For example, when we multiply 1 * 2 = 2, this number is already present in the list, which creates a duplicate and can break the chronological order of the nth value. Thus, multiplying 2 * 3 = 6 and then 3 * 2 = 6 again would also cause an issue. The sequence of the first 10 ugly numbers (has duplicates excluded) is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12. How do we solve this problem? We can maintain an additional data structure to indicate if an element has already been created. What data structure do you suggest? A list could be used, but its lookup time could be as bad as O(n). Alternatively, a hashmap could be used; it would provide O(1) lookup time and allow us to easily add new numbers if they are not already present in the existing ugly numbers hashmap.
8. Ugly numbers are not created in order
1. Let's start over. We start building the ugly numbers again. Start with 1, multiply it by 2, 3, 5. This gives us (1,2,3,5) There was another problem: were these the first 4 ugly numbers? (1, 2, 3, 4) Are the first 4 ugly numbers, instead of (1,2,3,5) Before 1 is supposed to be multiplied by 5. 2 needs to be multiplied by 2.
Copy

first = 1
first(1) , second (2), third(3), fifth (5) 

missing forth (4)

Copy

i = first Ugly number
i , i + 1, i + 2, i + 3 ... n

9. The order matters.
1. We have many ugly numbers that are not created in order. Even when we have created n ugly Numbers. We might be missing alot in between. Not to mention we will have to sort them everytime we get new values in. As 4 will be created in the next iteration when 2 is multiplied by 2.
2. Multiplying 2*2 gives us 4, which cannot be simply added to the array as it would disrupt the order of the elements created and thus the nth number. We need to keep the newly genreated elements in an a array and sort it every time we add new numbers, which can cost us O(nlogn) complexity for each time we add all the newly created ugly numbers in. This can get really complicated as we keep creating ugly numbers. Time Complexity: O(n * nlog(n))
3. After accounting for duplicates, the numbers created in this way are ugly but not in order.
Copy

2 * 1 = 2
3 * 1 = 3
5 * 1 = 5
2 * 2 = 4
3 * 2 = 6
5 * 2 = 10
3 * 3 = 9
5 * 3 = 15

10. There must be a better way. A greedy way? We can instead generate them in order and stop when we get to the n.
11. If i is the order of the ugly number. i needs to be equal to n for it to return the nth ugly number
1. i = 1 first ugly number is one we already have it.
2. How do we get i = 2? By multiplying 1 by 2, 3 or 5. The smallest result will be the 2nd ugly number.
3. From all the ugly numbers created up to that point we take the smallest which is [1] we know that since it is the set of 1 it will be the smallest multiplying it with the set of prime factors (2,3,5). Will give us one value that is the next ugly number.
4. The smallest number in the list is 2, which will be the second ugly number (i=2) [(2),3,5] . Multiply it by the prime factors of 2, 3, and 5 to create new ugly numbers.
5. The smallest number in the list is 3, which will be the third ugly number(i = 3) [(3), 5, 4, 6, 10]. Multiply it by the prime factors of 2, 3, and 5 to create new elements and obtain the result.
6. Will have to exclude the ith ugly number (1,2,3 in the above cases) that we used to create other ugly numbers as we don’t need them to create next ugly numebers. Even if we do they will give us duplicates. Once we have ran the process (n - 1) times we will have the nth number as our smalles value amongst all the numbers created.
7. At every iteration, we are left with the smallest candidate to multiply to create the next ugly number. Starting from one, we multiply the smallest ugly number (n-1) times. Therefore, after (n-1) iterations, the nth ugly number is at the the start of the list. The reason for using n-1 instead of n is that 1 is already an ugly number adn created, so there was no need to multiply anything to it.
Copy

[1(smallest)] for 1
(exclude) = [1] [2(smallest), 3, 5] for 2 
(exclude) = [1,2] [3(smallest), 4, 5, 6, 10] for 3
(exclude)= [1, 2, 3] [4(smallest), 5, 6, 9, 10, 15] for 4
(exclude)= [1, 2, 3, 4] [5(smallest), 6, 8, 9, 10, 12, 15, 20] for 5
(exclude)= [1, 2, 3,4,5] [6(smallest), 8, 9, 10, 12, 15, 20, 25] for 6
(exclude)= [1, 2, 3, 4, 5, 6] [8(smallest), 9, 10, 12, 15, 18, 20, 25, 30] for 7

8. We know now:
1. Each iteration will give us the ith ugly number if we create the ugly number using the smallest ugly number from the last iterations.
1. This will require us to sort all the ugly numbers created and get the smallest one. As the ith ugly number.
2. Excluding any ugly numbers used previously.
3. Also excluding any duplicates created in the process.
4. The nth ugly number will be available at the start of the array the nth iteration
1. Since we already have 1 we don’t add consider that an iteration in the for loop. So the for loop will have n-1 iterations.

Code

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        allowedPrimes = [2, 3, 5]
        existing = {1}
        arr = [1]

        for _ in range(n - 1):
            smallestUgly = arr[0]
            for factor in allowedPrimes:
                possibleUglyNumber = smallestUgly * factor
                if possibleUglyNumber not in existing:
                    existing.add(possibleUglyNumber)
                    arr.append(possibleUglyNumber)
            arr.pop(0)
            arr.sort()

        return arr[0]

Complexities

Time Complexity: O(n*(nlogn))

Space Complexity: O(n)

Sandbox (press on Edit code to try with your own inputs)

Further Optimization

1. We only need the minimum number from the whole set of list and want to keep the order sorted to return the minumum again as new ugly numbers are added, We only need the smallest ugly number so we can sacrifice the whole sortedness of the list just for the smallest ugly number we can use a heap to reduce the complexity from O(nlogn) to O(log(n)).

The heap data structure allows us to maintain partial sorting of the data

1. Partial sortedness means the whole array is not sorted but to the top element is either the maximum or the minimum. For more information, please refer to A heap upclose: Simulating a max heap
2. The nth ugly number is always at the top of the min heap after the (n-1) th iteration. This is because it is the smallest number in the heap that has not yet been multiplied to create the next ugly number. All ugly numbers greater than it, which might have been created in the last iteration or are not used in previous iterations, sink to the bottom of the heap. Once the element is poped out of the heap we never place it back. At every iteration, we are left with the smallest candidate to multiply to create the next ugly number. Starting from one, we multiply the smallest ugly number (n-1) times. Therefore, after (n-1) iterations, the nth ugly number is at the top. For example, for the 4th number, the 4th ugly number was at the top of the min heap after the 3rd iteration (n-1). The reason for using n-1 instead of n is that 1 is already an ugly number adn created, so there was no need to multiply anything to it.
Copy

start = [1]

smallest ugly = 1 
iteration 1 = [1]
	pop 1 out multiply it by 2,3,5 add them to the heap -> [2, 3, 5]

smallest ugly = 2 
iteration 2 = [2, 3, 5] smallest ugly = 2 
	pop 2 out multiply it by 2,3,5 add them to the heap -> [3, 5, 4, 6, 10]

smallest ugly = 3 
iteration 3 = [3, 5, 4, 6, 10]
	pop 3 out multiply it by 2,3,5 add them to the heap -> [4, 5, 10, 6, 9, 15]

smallest ugly = 4
[4, 5, 10, 6, 9, 15]

For nth = 4 we will find our nth ugly number at 3rd iteration(n-1)

Code

from heapq import heappop, heappush
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        
        
        allowedPrimes = [2,3,5]
        existing = {1}
        minHeap = [1]


        for _ in range(n-1):
            
            smallestUgly = heappop(minHeap)
            for factor in allowedPrimes:
                
                possibleUglyNumber =  smallestUgly * factor

                if possibleUglyNumber not in existing:
                    heappush(minHeap,possibleUglyNumber)
                    existing.add(possibleUglyNumber)
        

        return minHeap[0]

Complexities

Time Complexity: O(n log n)

Each deletion and insertion takes O(log n) time. The constant factor is 3 (added to the heap at each iteration) which will not effect the time complexity. Since this is done n-1 times, the total time complexity reduces to O(n log n).

Space Complexity: O(n)

Numbers increase linearly as one is removed and three added, resulting in a difference of two. No duplicates are added, so it's not exactly one-to-one, but theoretically O(n).

Sandbox (press on Edit code to try with your own inputs)