Page 10 of 11
Posted: Mon Oct 08, 2007 9:19 pm
by Mpouzas
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
Without storing already calculated numbers...
Posted: Fri Jun 20, 2008 5:29 pm
by dreadlord
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
Re: 136 Ugly number WA
Posted: Mon May 11, 2009 7:43 pm
by rahat089
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;
}
Re: 136 Ugly Number Presentation Error
Posted: Fri Sep 04, 2009 12:42 pm
by aliahmed
You're just missing "\n";
remove after accepted
Re: 136 Ugly Number Presentation Error
Posted: Sat Oct 17, 2009 3:18 am
by prodhan
where to include "\n"
I am trying it in more & more in diff positions but getting WA.
Re: 136 Ugly Number Presentation Error
Posted: Tue Oct 27, 2009 2:07 pm
by r2ro
Code: Select all
printf("The 1500'th ugly number is %d.\n",ugly[1499]);
There you go. Remove your code afterwards
.
problem 136
Posted: Sat Oct 30, 2010 8:44 pm
by mustak0715
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
136 ugly numbers run time error
Posted: Sun Feb 20, 2011 9:13 pm
by dream
#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??
Re: problem 136
Posted: Wed Mar 16, 2011 1:44 pm
by shiam
no.. try again..it is bigger than your ans....
Ugly Number(136)
Posted: Fri Oct 05, 2012 5:24 pm
by mainul07
#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 
Re: Ugly Number(136)
Posted: Fri Oct 05, 2012 8:11 pm
by brianfry713
unsigned long result[1500];
This line only allocates space for result[0] through result[1499], then you try to print result[1500]
Re: Ugly Number(136)
Posted: Sat Oct 06, 2012 11:21 am
by mainul07
Thanks
136 Ugly number
Posted: Sat Apr 06, 2013 9:03 am
by nilaunog
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;
}
Re: 136 Ugly number
Posted: Tue Apr 09, 2013 3:06 am
by brianfry713
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>.
Re: 136 Ugly number
Posted: Tue Oct 01, 2013 1:38 pm
by t_sleepy
The following code is giving me wrong answer. Please tell me what is wrong with the code.
#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;
}