136 - Ugly Numbers

[necropower]

hey guys, i solved the 136 problem[ugly numbers] , but i cant see HOW can i solve it in 0 SECONDS!! i take at least 3 or 4 seconds to do that[using quicksort in a array] , is there a equation to solve that problem? can u help me??

[[]] Necropower

[Ivor]

Well isn't it obvious? Just use your imagination a bit

Ivor

[necropower]

dont tell me that u r using RETURN ANSWER...
i refuse to do that, it is cheating...

if it isnt that way, cant u help me?

[Ivor]

I haven't solved the problem and I'm not in the mood for trying, but it is the only adequate way I can think of from the first sight.

...and I wouldn't call it cheating. Let's just say it's efficient.

Ivor

[chrismoh]

well, there is an O(n log n) method.

for n=1500, it should finish nearly instantly.

There is also a lazy O(n^2) method that should work pretty fast.

<font size=-1>[ This Message was edited by: chrismoh on 2001-12-28 09:26 ]</font>

[necropower]

and how is that? how is that n^2 and the nlogn methods?

[chrismoh]

Note: Spoiler. If you want to solve this question by yourself, don't look at this now.

































































O(n^2):
Every ugly number other than 1 has the property that it = 2,3, or 5 multiplied by some other ugly number.

Therefore, what can be done is the following:
Store a list of ugly numbers. To obtain the next ugly number, look through the list of already generated ugly numbers, multiply each and every one by 2,3 and 5, and take the smallest number generated bigger than the currently largest ugly number.
To obtain the ith ugly number, you will have to check (i-1) ugly numbers. This leads to an O(n^2) algorithm.

O(n log n):
(1)Begin with a heap containing the numbers 2,3,5, with the current ugly number 1.
(2)Pop the smallest number from the heap.
(3)Repeat step (2) until the number popped is bigger than the current ugly number
(4)Let the ugly number found be x. Push numbers x*2,x*3,x*5 on the heap
(5)Repeat steps (2)-(4) until n ugly numbers are found.

Maximum size of the heap is 3*n. Step (2) is thus done at most 3*n times. Step (4) is done at most n times. Step (2) and Step (4) each have complexity O(log n), thus the complexity of this algorithm is O(n log n).

There is an improvement on this method that reduces the constant factor hidden in the O-notation, but requires more space:

With each ugly number in the heap, store the largest prime factor (i.e. 2,3 or 5) of that number. Let us say the number obtained after step (3) is x and its largest prime factor is z. Then push only values x*p into the heap where p is a prime in {2,3,5} >= z. This makes step (3) redundant.

Does anyone know if there is an O(n) algorithm?

<font size=-1>[ This Message was edited by: chrismoh on 2001-12-29 01:14 ]</font>

[SilentStrike]

Can someone tell me what is wrong with this solution?

I came up with this method independantly, originally had just a priority_queue, but had troulbe with duplicates, rather than popping them out and keeping track of current ugly number, I used a set as well, slower, but still O(nlog(n)).

#include <stdio.h>
#include <queue>
#include <iostream>
#include <set>

struct lowerNumIsGreaterPriority {
bool operator()(int a, int b) {
return a > b;
}
};

bool addedIfNew(std::set<int>& intSet, int num) {
std::set<int>::iterator i = intSet.find(num);
if (i == intSet.end()) {
intSet.insert(num);
return true;
}
return false;
}

const int N = 1500;

int main(int argc, char *argv[])
{
std::set<int> contents;
std::priority_queue<int, vector<int>, lowerNumIsGreaterPriority> pq;
contents.insert(1);
pq.push(1);

while (contents.size() < N) {
int newNum = pq.top();
// cout << "t" << contents.size() << "t" << newNum << "n";
pq.pop();
if (addedIfNew(contents, newNum*2)) {
pq.push(newNum*2);
}
if (addedIfNew(contents, newNum*3)) {
pq.push(newNum*3);
}
if (addedIfNew(contents, newNum*5)) {
pq.push(newNum*5);
}
}
/* while (pq.size() > 1) pq.pop();
cout << "The " << N <<"'th ugly number is " << pq.top() << ".";
*/
std::set<int>::iterator i = contents.begin();
for (int count = 0; count < N - 1; count++) {
// cout << *i << endl;
i++;
}
cout << "The " << N <<"'th ugly number is " << *i << ".";
char wait; cin >> wait;
return 0;
}

<font size=-1>[ This Message was edited by: SilentStrike on 2002-01-04 00:58 ]</font>

[paulhryu]

How about this? It works in like 0.3 seconds.

// @BEGIN_OF_SOURCE_CODE

/* @JUDGE_ID: 17243NT 136 C++ "O(n^2) algorithm" */

// Send to judge@uva.es

#include <iostream.h>

const int INF = 1000000000;

int main() {
int i, j;
int ugly[1500];

ugly[0] = 1;

for(i = 1; i < 1500; i++) {
ugly = INF;

for(j = 0; j < i; j++) {
if(ugly[j] * 2 > ugly) {
if(ugly[j] * 2 < ugly) ugly = ugly[j] * 2;
} else if(ugly[j] * 3 > ugly) {
if(ugly[j] * 3 < ugly) ugly = ugly[j] * 3;
} else if(ugly[j] * 5 > ugly) {
if(ugly[j] * 5 < ugly) ugly = ugly[j] * 5;
}
}
}

cout << "The 1500'th ugly number is " << ugly[1499] << ".n";

return 0;
}

// @END_OF_SOURCE_CODE

[Stefan Pochmann]

Linear solution, Chris? Sure, why not. But I'm sure you want to find out yourself how it can be done. Moreover, I don't really want to publish my solution here.

Thank you so much for asking this question. I've always been totally in love with this problem. And thanks to you I now tried to do it in O(n) and succeeded. Btw, it's actually not that hard...

This problem was the first time I applied dynamic programming, long before I knew that somebody had already discovered this technique ... Oh yeah... I was young and without knowledge

Stefan

[Zheng]

to Stefan Pochmann:
using the priority queue(a heap) in C++
I can slove the problem in 0.00 sec

but not O(n)
how does dynamic programming work in this problem?

some persons used this
[cpp]void main()
{
cout<<"The number is xxxxxxx";
}[/cpp]
they said the algorithm was "Preprocessing"

[Stefan Pochmann]

Hmm, now that I think about it again, I'm not sure if I should call it dynamic programming. Yes, now I can even reconstruct the mistake. The real first DP solution I wrote was for 147 (Dollars). My solution here does not really use DP. Sorry about that, can't explain how that happened.

Now that this is cleared, let me say more precisely that I can calculate *all* ugly numbers up the the n-th in sorted order in time O(n). Should I post another hint? (Maybe I should create one of these cool polls for it

Oh yes, the good old preprocessing "algorithm"...

[taj79]

ugly numbers will be of the form
2^p * 3^q * 5^r

what i tried to that was first collecting integers of this form by using

for(r=0;r<15;r++)
for(q=0;q<15;q++)
for(p=0;p<15;p++)
{ ++t;
u = (int) ( pow(2,p)*pow(3,q)*pow(5,r) );
A[t]=u;
}
Then i applied quicksort on the elements of the array A.
Even if take A as array of double it exceeded the limit of datatype.
what should I do?

[Stefan Pochmann]

I don't believe you that you exceed double range with that program. (2*3*5)^15 is way smaller than what doubles can hold.

[taj79]

Yeah you were correct.the mistake I had done was that i was converting the double into int.

But I am not getting the correct answer .Is my way the correct way of solving this problem?