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

Mpouzas
New poster
Posts: 1
Joined: Sat Oct 06, 2007 12:36 am

Post by Mpouzas » Mon Oct 08, 2007 9:19 pm

Well it's a quite tricky problem...

The problem is clearly stated, It doesn't say to calculate the 1500'th and then print it. It just says to print the num...

ofcourse you have to come up with an algorithm that calculates the num...

since you find it, and believe me it takes a long time to do so... Just print the BLOODY NUMBER!!!:D


so a code like the one below
//////////////////////////////////////
#include <iostream>

int main( void ) {
std::cout << "The 1500'th number is " << 0000000000<< '.'
<< std::endl;
return 0;

}
/////////////////////////////////////

will just do

dreadlord
New poster
Posts: 19
Joined: Sat Apr 19, 2008 11:19 pm

Without storing already calculated numbers...

Post by dreadlord » Fri Jun 20, 2008 5:29 pm

Hio wrote:I tried with a straight-to-the-problem solution, i mean i made a procedure that returns 1 if a given number is ugly and 0 otherwize. Well as you can suppose the result needs a lot of time.
The function is that:

[...]

If some one can find a way to speed this up. I will be greatfull for help.
Thanks
Hi, Hio.

I guess it's "a bit" late for this reply to be helpful to you, but perhaps it could be for someone else (including myself).

If when you ask for "a way to speed this up" you mean a way to solve this problem as it is described, in former posts of this same thread you may find very smart ways to do so. But if you mean a way to calculate ugly numbers without storing all the already calculated previous ones, as you are doing in your algorithm, I believe this could help you.

My first attempt to solve this problem was exactly this way. I wrote a function with which you may calculate the next ugly number from the previous one N in a time in O( [log(N)]^3) with very good constants. I made just a prototype of the algorithm in Octave, as it took an execution time of about 6s to reach the 1500th number, which in practical terms means that the equivalent Pascal/C/C++ algorithm hardly could get below the problem time limit, so I gave up with this idea.

Here you may find my Octave function. I believe it's quite easy to read, though you don't know programming in Octave (BTW, it also works perfectly in MATLAB).

Code: Select all

function [res, pruebas] = sigp235(num)
% function [res, pruebas] = sigp235(num)
%
% Returns in 'ret' the lesser number which is greater or equal to 'num'
% that can be factorized in 2, 3, and 5, i.e., can be expressed as
% res = 2^i * 3^j * 5^k, with i, j, and k natural.
% So if 'num' matches this property, it returns the same value 'num'.
% If two results are specified in the call, returns in 'pruebas'
% the number of attempts evaluated (candidate numbers considered).
%

%
p2max = ceil (log(num) / log(2));
p3max = ceil (log(num) / log(3));
p5max = ceil (log(num) / log(5));
%
maxp2 = 2^p2max;
maxp3 = 3^p3max;
maxp5 = 5^p5max;
%
best_est = min (maxp2, min (maxp3, maxp5));
if best_est == num,
	res = best_est;
	if nargout == 2,
		pruebas = 3;
	end
	return;
end;
%
pbas = 3;
%
f5 = maxp5;
for p5 = 1:p5max,
    f5 = f5 / 5;
    factor5 = num / f5;
    p3max = ceil (log(factor5) / log(3));
    f3 = 3^p3max;
    for p3 = 0:p3max,
		factor53 = factor5 / f3;
		p2max = ceil (log (factor53) / log(2));
		f2 = 2^p2max;
		for p2 = 0:p2max,
			attempt = f5 * f3 * f2;
			pbas = pbas + 1;
			if attempt == num,
				res = num;
				if nargout == 2,
					pruebas = pbas;
				end
				return;
			elseif attempt > num && attempt < best_est,
				best_est = attempt;
			elseif attempt < num,
				break;
			end
			f2 = f2 / 2;
		end
		f3 = f3 / 3;
	end
end
res = best_est;
if nargout == 2,
	pruebas = pbas;
end
With this function you may easily calculate the N'th ugly number by means of the following simple script:

Code: Select all

nfound = 1; tried = 1;
for nfound=2:N,
	tried = sigp235 (tried+1);
end
printf ("%d => %lu\n", N, tried);
If anyone else has a better way to calculate ugly numbers without storing all the previous ones, I would appreciate it if he/she were so nice to share his/her knowledge with me.

c u,

--Dread

rahat089
New poster
Posts: 2
Joined: Sat May 02, 2009 5:03 pm

Re: 136 Ugly number WA

Post by rahat089 » Mon May 11, 2009 7:43 pm

i am gettin wrong ans with this code...can anyone plz help me out with this???


#include<stdio.h>
int p;
int q;
int r;
int ugly[1501]={0};
int main()
{
int P,Q,R;
ugly[0]=1;
p=q=r=0;
int i=1;
while(ugly[1499]==0)
{
P=(ugly[p])*2;
Q=(ugly[q])*3;
R=(ugly[r])*5;
if((P<Q)&&(P<R))
{
ugly=P;
i++;
p++;
}
else if((Q<P)&&(Q<R))
{
ugly=Q;
i++;
q++;
}
else if((R<P)&&(R<Q))
{
ugly=R;
i++;
r++;
}
else if(P==Q)
{
q++;
}
else if(P==R)
{
r++;
}
else if(R==Q)
{
r++;
}

}
printf("The 1500'th ugly number is %d",ugly[1499]);
return 0;
}

aliahmed
New poster
Posts: 24
Joined: Fri Oct 24, 2008 8:37 pm
Location: CUET, Chittagong, Bangladesh
Contact:

Re: 136 Ugly Number Presentation Error

Post by aliahmed » Fri Sep 04, 2009 12:42 pm

You're just missing "\n";
remove after accepted

prodhan
New poster
Posts: 2
Joined: Sat Oct 17, 2009 3:07 am

Re: 136 Ugly Number Presentation Error

Post by prodhan » Sat Oct 17, 2009 3:18 am

where to include "\n"
I am trying it in more & more in diff positions but getting WA.

r2ro
New poster
Posts: 38
Joined: Thu Sep 25, 2008 9:26 am

Re: 136 Ugly Number Presentation Error

Post by r2ro » Tue Oct 27, 2009 2:07 pm

Code: Select all

printf("The 1500'th ugly number is %d.\n",ugly[1499]);
There you go. Remove your code afterwards ;).

mustak0715
New poster
Posts: 3
Joined: Tue Oct 26, 2010 3:42 am

problem 136

Post by mustak0715 » Sat Oct 30, 2010 8:44 pm

is this correct the 1500th ugly number is 2999.
please say me anyone.
here is code where is error;
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
vector<long>ugly;
vector<long>list;
vector<long>::iterator it;
vector<long>::iterator u;

void primegenerate(long n)
{

//list.push_back(2);
for(long i=7;i<=n;i+=2)
{
list.push_back(i);//list create
}
for(long p=3;p*p<=n;p+=2)
{
for(it=list.begin()+1;it<list.end();)
{
if(*it%p==0 && *it!=p)
{
list.erase(it);//erase

}
else
it++;
}
}

i=0;
/*for(it=list.begin();it<list.end();it++,i++)
{
cout<<i<<" "<<list<<" ";
}*/
}

void print(int number)
{
//int i=0;
u=ugly.begin();
u=u+number-1;
cout<<"The "<<number<<"th ugly nmber is "<<*u;
// for(it=ugly.begin();it<ugly.end(),i<1500;it++,i++)
// {cout<<i<<" "<<*it<<endl;
// }
}

int main()
{
int counter=0;

for(long i=7;i<3000;i++)
{
if(i%2||i%3||i%5)
{

ugly.push_back(i);

//cout<<ugly[counter]<<" ";
counter++;}

}
cout<<counter;

primegenerate(1600);

//cout<<list.size();
long num,den;
u=ugly.begin();
for(u=ugly.begin();u<ugly.end();)
{
for(it=list.begin();(*it)*(*it)<=(*u)||it<list.end();it++)
{
num=*u;den=*it;
if(num%den==0)
{
ugly.erase(u);//erase
break;
}

}
u++;
}

//int number;
//while(1){

u=ugly.begin();
for(i=1;i<=6;i++)
{
ugly.insert(u,1,i);
u++;
}
//while(1){
//cin>>number;

print(1500);
//cout<<ugly.size()<<" "<<ugly[1500];

return 0;
}
u can mail me at mahmed0715@yahoo.com

dream
New poster
Posts: 3
Joined: Sat Feb 19, 2011 4:40 pm

136 ugly numbers run time error

Post by dream » Sun Feb 20, 2011 9:13 pm

#include<stdio.h>
int main()
{
unsigned long int a,b,flag,loop=6;
for(a=7;;a++)
{
if((a%2==0)||(a%3==0)||(a%5==0))
{
flag=0;
for(b=6;b<a;b++)
{
if((b%2!=0)&&(b%3!=0)&&(b%5!=0))
{
if(a%b==0)
{
flag=1;
break;
}
else
flag=2;
}
}
if(flag==2)
loop=loop+1;
}
if(loop==1500)
{
printf("The 1500'th ugly number is %li.\n",a);
break;
}
}
return 0;
}


here is my code
plz help me
what's the problem??

shiam
New poster
Posts: 8
Joined: Mon Mar 14, 2011 6:44 am

Re: problem 136

Post by shiam » Wed Mar 16, 2011 1:44 pm

no.. try again..it is bigger than your ans....

mainul07
New poster
Posts: 8
Joined: Fri Oct 05, 2012 1:35 pm
Location: Chittagong
Contact:

Ugly Number(136)

Post by mainul07 » Fri Oct 05, 2012 5:24 pm

#include<stdio.h>
unsigned long findmin();
unsigned long temp[3];
int main()
{
unsigned long store[3];
unsigned long result[1500];
int i,j,n;
unsigned long receive;
result[1]=1;
for(i=0;i<3;i++)
store=1;
for(i=2;i<=1500;i++)
{
temp[0]=result[store[0]]*2;
temp[1]=result[store[1]]*3;
temp[2]=result[store[2]]*5;

receive=findmin();
for(j=0;j<3;j++)
if(temp[j]==receive)
store[j]++;
result=receive;
}

printf("The 1500'th ugly number is %lu.\n",result[1500]);

return 0;
}
unsigned long findmin()
{
int i,j;
unsigned long min=temp[0];
for(i=1;i<3;i++)
if(min>temp)
min=temp;
return 0;
}


When i submit it in uva it show WA.I can not find any error please help me :-?
Mainul Hassan
Website:http://www.teronga.com/

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Ugly Number(136)

Post by brianfry713 » Fri Oct 05, 2012 8:11 pm

unsigned long result[1500];
This line only allocates space for result[0] through result[1499], then you try to print result[1500]
Check input and AC output for thousands of problems on uDebug!

mainul07
New poster
Posts: 8
Joined: Fri Oct 05, 2012 1:35 pm
Location: Chittagong
Contact:

Re: Ugly Number(136)

Post by mainul07 » Sat Oct 06, 2012 11:21 am

Thanks :)
Mainul Hassan
Website:http://www.teronga.com/

nilaunog
New poster
Posts: 1
Joined: Sat Apr 06, 2013 8:51 am

136 Ugly number

Post by nilaunog » Sat Apr 06, 2013 9:03 am

what is the mistake of the following code?? plz help me??
#include<stdio.h>
int main()
{
long long int i=1,j,k,l;
long long int num, count=1;
while(count==1500)
{
for(i=1;i<=num;i++)
{
k=0;
if(num%i==0)
{
for(j=1;j<=i;j++)
{
if(i%j==0)
k++;

}
if(k==2)
{
l=i;
}
}
}
if((l==2)||(l==3)||(l==5))
{

count++;

}


}
printf("%d",num);


return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 136 Ugly number

Post by brianfry713 » Tue Apr 09, 2013 3:06 am

Your code just prints 0.

Output should consist of a single line as shown below, with <number> replaced by the number computed.

Sample output

The 1500'th ugly number is <number>.
Check input and AC output for thousands of problems on uDebug!

t_sleepy
New poster
Posts: 2
Joined: Tue Oct 01, 2013 1:32 pm

Re: 136 Ugly number

Post by t_sleepy » Tue Oct 01, 2013 1:38 pm

The following code is giving me wrong answer. Please tell me what is wrong with the code. :roll:

#include<stdio.h>
#define min(x,y) ((x)<(y)? x:y)
int main()
{
long u[1520];
int i,a=1,b=1,c=1,x,y,z;
u[1]=1;
u[2]=1;
u[3]=1;
for(i=2;i<=1500;i++){
x=2*u[a];
y=3*u;
z=5*u[c];
u= min (x,min(y,z));
if (u==x) a++;
if (u==y) b++;
if (u==z) c++;
}
printf("The 1500'th ugly number is %ld.",u[1500]);
return 0;
}

Post Reply

Return to “Volume 1 (100-199)”