136 - Ugly Numbers

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

necropower
New poster
Posts: 20
Joined: Wed Dec 26, 2001 2:00 am
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
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
Well isn't it obvious? Just use your imagination a bit Ivor

necropower
New poster
Posts: 20
Joined: Wed Dec 26, 2001 2:00 am
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
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
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
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA
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
New poster
Posts: 20
Joined: Wed Dec 26, 2001 2:00 am
and how is that? how is that n^2 and the nlogn methods?

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA
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
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 2002-01-04 00:58 ]</font>

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

// @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;

ugly = 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 << ".n";

return 0;
}

// @END_OF_SOURCE_CODE

Stefan Pochmann
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

Zheng
New poster
Posts: 6
Joined: Mon May 06, 2002 12:27 pm
Location: Xi'an, China
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
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 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
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

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?

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
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
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
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?