136  Ugly Numbers
Moderator: Board moderators

 New poster
 Posts: 20
 Joined: Wed Dec 26, 2001 2:00 am

 New poster
 Posts: 20
 Joined: Wed Dec 26, 2001 2:00 am

 New poster
 Posts: 20
 Joined: Wed Dec 26, 2001 2:00 am
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 (i1) 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 Onotation, 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 20011229 01:14 ]</font>
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 (i1) 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 Onotation, 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 20011229 01:14 ]</font>

 New poster
 Posts: 22
 Joined: Fri Jan 04, 2002 2:00 am
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 20020104 00:58 ]</font>
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 20020104 00:58 ]</font>
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
// @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

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
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
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

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
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 nth 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"...
Now that this is cleared, let me say more precisely that I can calculate *all* ugly numbers up the the nth 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"...
Please give me hint for prob 136
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?
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?

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact: