136 - Ugly Numbers

[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

[dreadlord]

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]

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]

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

[prodhan]

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

[r2ro]

Code: Select all

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

There you go. Remove your code afterwards .

[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

[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??

[shiam]

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

[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

[brianfry713]

unsigned long result[1500];
This line only allocates space for result[0] through result[1499], then you try to print result[1500]

[mainul07]

Thanks

[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;
}

[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>.

[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;
}