UGLY NUMBERS
Even numbers could be ugly!!!! I suddenly find number systems and C to be greatly interesting :) :)
Recently going through the net I found a question...
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
shows the first 11 ugly numbers.
By convention, 1 is included.
We need to find 1500'th ugly number.
---------------------------------------------Best solution according to me--------------------------------------------------
if x is ugly, then so are 2x, 3x and 5x.
So we can use a min-heap.
Start with 1 in the heap.
Now if we do the following in a loop:
x = Heap.PopCurrentMin();
Heap.Insert(2x);
Heap.Insert(3x);
Heap.Insert(5x)
I believe this will work. Not sure what the time complexity will be, but my guess is that this is reasonably efficient. :) If any one finds a better solution....Please do post!!!!
Recently going through the net I found a question...
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
shows the first 11 ugly numbers.
By convention, 1 is included.
We need to find 1500'th ugly number.
---------------------------------------------Best solution according to me--------------------------------------------------
if x is ugly, then so are 2x, 3x and 5x.
So we can use a min-heap.
Start with 1 in the heap.
Now if we do the following in a loop:
x = Heap.PopCurrentMin();
Heap.Insert(2x);
Heap.Insert(3x);
Heap.Insert(5x)
I believe this will work. Not sure what the time complexity will be, but my guess is that this is reasonably efficient. :) If any one finds a better solution....Please do post!!!!
Comments