136  Ugly Numbers
Moderator: Board moderators
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
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...
Hi, Hio.Hio wrote:I tried with a straighttotheproblem 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
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
Code: Select all
nfound = 1; tried = 1;
for nfound=2:N,
tried = sigp235 (tried+1);
end
printf ("%d => %lu\n", N, tried);
c u,
Dread
Re: 136 Ugly number WA
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;
}
#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;
}

 New poster
 Posts: 24
 Joined: Fri Oct 24, 2008 8:37 pm
 Location: CUET, Chittagong, Bangladesh
 Contact:
Re: 136 Ugly Number Presentation Error
You're just missing "\n";
remove after accepted
remove after accepted
Re: 136 Ugly Number Presentation Error
where to include "\n"
I am trying it in more & more in diff positions but getting WA.
I am trying it in more & more in diff positions but getting WA.
Re: 136 Ugly Number Presentation Error
Code: Select all
printf("The 1500'th ugly number is %d.\n",ugly[1499]);

 New poster
 Posts: 3
 Joined: Tue Oct 26, 2010 3:42 am
problem 136
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+number1;
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%2i%3i%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
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+number1;
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%2i%3i%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
#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??
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
no.. try again..it is bigger than your ans....
Ugly Number(136)
#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
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/
Website:http://www.teronga.com/

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: Ugly Number(136)
unsigned long result[1500];
This line only allocates space for result[0] through result[1499], then you try to print 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!
136 Ugly number
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;
}
#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;
}

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 136 Ugly number
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>.
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!
Re: 136 Ugly number
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;
}
#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;
}