## 136 - Ugly Numbers

Moderator: Board moderators

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
BTW = By The Way

And sorry for my offensiveness. Every once in a while I get tired and say mean things I shouldn't. But you really asked some questions that you could've easily answered yourself, I think. Try finding things out yourself, otherwise you'll always depend on others to help you... for example enter "acronym" and "btw" in Google and with the first page you'll find out that
BTW = Belasting over de Toegevoegde Waarde (or that other meaning I gave above)

(Also, I just found out that I had mistaken you for somebody else...)

naps90
New poster
Posts: 1
Joined: Fri Nov 08, 2002 9:07 pm

### 160 answear

necropower wrote: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
preprocess then output is fine.
However,I think I have an O(n) method (very fast,the constant is
3 or less).
I posted it,but I get WA.
Can I send you my ansear (and the linear algorithm and just tell me wether it was your answear.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Yeah, show me your linear time algorithm. I'd be happy to talk about our solutions.

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

### just solved it n.log(n)

of course i cheated and sent a lame

[c]#include <stdio.h>
int main()
{
printf("The 1500'th ugly number is ********.\n");
return 0;
}[/c]

BUT here is the explanation of my N LOG N algo:

my algo was as follow... store the ith first ugly numbers in an array.
you know the i+1th ugly number is an ugly number ou already know multiplied by 2, 3 or 5.
so you try to guess this ugly number. it's easy, let's say the ith ugly number is N. you know the numbers you need to look for are close to N/2 N/3 and N/5.
call them mul2 mul3 and mul5, then all you have to do is pick the smallest among mul2*2, mul3*3 and mul5*5.

since looking for a number in an ordered array is log(n), and you do it n times, the solution is n.log(n) (roughly)

there is a constant = 3, due to the fact you look 3 times in the array.

please tell me how you did it if you have a log(n) algo, i'm really curious about it epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

### and here is my n.log(n) program that runs in 0.00 on my PC

[c]#include <stdio.h>

#define MIN(a,b,c) ((a) > (b) ? ((b) > (c) ? (c) : (b)) : ((a) > (c) ? (c) : (a)))

int ugly;

int find(int _max,int target)
{
int max = _max-1;
int middle;
int min = 0;
while (min < max)
{
middle = (min + max)/2;
if (ugly[middle] < target)
min = middle+1;
else
max = middle;
}
return ugly[max];
}

int main()
{
int k = 1500;
int mul2,mul3,mul5;
int i,target;
ugly=1;
for (i=1;i<k;i++)
{
target=ugly[i-1];
mul2 = find(i,target/2+1);
mul3 = find(i,target/3+1);
mul5 = find(i,target/5+1);
ugly = MIN(2*mul2,3*mul3,5*mul5);
}
printf("The %d'th ugly number is %d.\n",k,ugly[k-1]);
return 0;
}[/c]

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
epsilon0, you're very close to my linear time solution. The big difference is that I don't search for mul2, mul3 and mul5. I know where to look them up in constant time.

No idea about a logarithmic solution and I doubt that there is one. It's easy to see that an O(n) solution is optimal for the reporting variant (where you compute the first n ugly numbers), though, so I'm at least proud of that epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

### please drop a few hints

care to share your knowledge? i see why your solution is O(n). but how do you manage to look up ugly numbers in O(1)?
do you use a hash function?
seriously, you cannot have an array A big enough to store an ugly number U as A = 1; it has to be a hash... but i still don't see.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
No hash and no arrays as large as the numbers. Here's a spoiler: I have three queues, one for each prime factor, and the total number of numbers added to the queues doesn't exceed 3n.

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

### better solution... looks linear :D

ok i figured it's useless to test all the ugly numbers each time... the numbers you pick in each of the 3 queues are in ascending order.
so here's my solution with 3 "pointers":

[c]#include <stdio.h>

#define MIN(a,b,c) ((a) > (b) ? ((b) > (c) ? (c) : (b)) : ((a) > (c) ? (c) : (a)))

int ugly;

int main()
{
int k = 1500;
int index2=0, index3=0, index5=0;
int candidate2, candidate3, candidate5;
int i,target;

ugly=1;

for (i=1;i<k;i++)
{
target=ugly[i-1]+1;
while((candidate2 = 2 * ugly[index2]) < target) index2++;
while((candidate3 = 3 * ugly[index3]) < target) index3++;
while((candidate5 = 5 * ugly[index5]) < target) index5++;
ugly = MIN(candidate2, candidate3, candidate5);
}

printf("The %d'th ugly number is %d.\n",k,ugly[k-1]);
return 0;
}[/c]

i'm not sure it's linear... is this your solution? what do you think?

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
1) It is linear.
2) It is not exactly like mine.
3) It is better than mine.

Why?

1) Your whole work is done inside the loop, which is executed k-1 (or n-1, we called used to call it n) times. Inside you have two constant time commands and three loops. In one iteration of the outer loop, each inner loop could take long, but if you look at the computation as a whole, the time spend in each of the inner loops is O(k), since each "index" starts at 0, is increased with every inner loop iteration, never set back and never exceeds k. So even though a single outer loop iteration might take long, the overall average for one iteration is constant time. Similar to convex hull finding with Graham's Scan.

2) I have three queues, one for numbers that can still be multiplied by {2,3,5}, one for numbers that can still be multiplied by {3,5} and one for {5}. See below.

3) We both need linear time, but my memory usage is higher. Don't know how much, since for example my first queue only contains {1,2,4,8,16,...}, so you probably don't win much. The third queue gets k numbers pushed into it, but I don't know about the second one. And the situation might get worse if we look at the "superugly" numbers built from {2,3,5,7,11} or even more primes.

Here's mine:

[cpp]
#include <iostream>
#include <queue>
using namespace std;

int main () {

int factor[] = { 2, 3, 5 };
queue<int> lists;

//----- Everybody can only extend 1.
for( int i=0; i<3; ++i )
lists.push( 1 );

//----- Simulate by extending.
for( int i=1; i<1500; ++i ){

//--- Calculate next number for each factor.
int next;
for( int j=0; j<3; ++j )
next[j] = lists[j].front() * factor[j];

//--- Find the winner (factor with smallest next number).
int winner = 0;
for( int j=1; j<3; ++j )
if( next[j] < next[winner] )
winner = j;

//--- Extend.
for( int i=winner; i<3; ++i )
lists.push( next[winner] );
lists[winner].pop();

}

cout << "The 1500'th ugly number is " << lists.back() << ".\n";
}
[/cpp]

Btw, I'd suggest this minOfThree:

#define MIN(a,b) (((a)<(b)) ? (a) : (b))
#define MIN3(a,b,c) MIN(a,MIN(b,c))

I think this is less error-prone. Alternatively, I'd suggest you include the C++ header <algorithm> and then write

min( a, min( b, c ))

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

### actually it can be made even faster

your solution is pretty smart, especially the fact that you don't always add the new ugly numbers in all 3 queues... on the other hand this causes extra computation and i'm not sure it's worth it. i still don't fully understand how you manage to always have the 3 candidates in front of your queue.

i improved my program with the use of pointers:

[c]#include <stdio.h>

#define FINDME 1500
#define MIN(a,b) ((a)>(b)?(b):(a))
#define MIN3(a,b,c) MIN(a,MIN(b,c))

int ugly[FINDME];

int main()
{
int k = FINDME;
int *last = ugly, *next = ugly + 1, *end = ugly + k;
int *pointer2 = last, *pointer3 = last, *pointer5 = last;
int candidate2, candidate3, candidate5;
int target;

*last = 1;

while(next < end)
{
target = *last + 1;
while((candidate2 = 2 * *pointer2) < target) pointer2++;
while((candidate3 = 3 * *pointer3) < target) pointer3++;
while((candidate5 = 5 * *pointer5) < target) pointer5++;
*next++ = MIN3(candidate2, candidate3, candidate5);
last++;
}

printf("The %d'th ugly number is %d.\n",k,*last);
return 0;
}[/c]

and just to prove that it's possible to get a 0.000 without "cheating":

Your C program has solved Ok the problem 136 (Ugly Numbers)
in 0.000 seconds with low memory spent.
Congratulations!

wsarzynski
New poster
Posts: 19
Joined: Fri Oct 04, 2002 7:50 pm
Location: Warsaw, Poland
Your solution is really good. Myself, i learned from this
problem that judge accepts inline asm in c++.
I just used three loops for logarithms and "jo" instruction
to detect overflows.
I think under-linear complexity algorithm is possible if "easy & dense" subset of ugly numbers exists, ie for numbers of some special form you can know it's position in constant time, so you can localize your number.
Anybody seen something like this ? I tried, no results as for now.
Also, I draw ugly numbers in gnuplot, and in small scale with interpolation it seems like some fractal curve.

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

### 136 - Ugly Numbers

What is the answer actually ?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
42, of course!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact: nice DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)