Here's what you do:
- Store the number 1 in a set.
- Consider the smallest item, "n" in the set. That is counted as the next ugly number.
- Add the numbers n*2, n*3, and n*5 to the set.
- Remove n from the set.
- Repeat steps 2-4 until you reach the desired ugly count (1500).
Sets are unordered lists, and we want to always find the smallest number of the set as efficiently as possible. How do we do that? We can't just read every number in the set, or the problem scope quickly becomes O(n2). Can't have that.
Turns out there is an ideal data structure for handling this kind of thing, but it's something I haven't looked at since I was an undergrad. It's called a min-heap.
A heap is a special kind of binary tree, where every level of the tree is filled to maximum density. For instance, in a heap with 8 elements, you know that the top level has one node with exactly two children; each of those two children has two children (that makes 7), and the leftmost node at the third level has one child on the left.
The neat thing about using a heap is that because of its predictable structure, you can represent it using an expandable one-dimensional array. You don't have to mess with pointers or the other headaches of data structures. If you are looking for root.left.right, you just calculate the spot in the array and access element 4.
A min-heap is constructed in such a way that the children of each node are guaranteed to be larger than the parent node. In other words, the smallest value is guaranteed to be at the root, and each child of the root is itself a min-heap with the smallest element of that at the root.
(If I'm going too fast for you, speak up. I don't believe I've ever done a post specifically on binary trees, so maybe I should.)
In any case... you can do two things with a min-heap: add a new element, which is rapidly sorted to the right place; and remove the root element, which then moves the next smallest element into the root and fixes the rest of the heap so that it is still a min-heap.
This is exactly what we need. It keeps the cost of searching for the smallest known ugly number to O(log n), where n is the number of elements currently in the list.
So to recap:
- Write your own min-heap class, which is the fun part. ;)
- Add the number 1 to the heap.
- Inspect the root of the heap, and count that number ("r") as ugly.
- Add 2r, 3r, and 5r to the heap.
- Delete the root.
- Repeat steps 3-5 until you reach the desired ugly count (1500).
And there you go. Small storage space, quick execution time, ignores non-ugly numbers, and finishes in 3 seconds easily.
In case you wondered, the answer is 859,963,392.