V = 2^i * 3^j * 5^k, how 2 work out the problem efficiently?

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
lotoren
New poster
Posts: 6
Joined: Sun Dec 23, 2007 11:11 am
Location: China

V = 2^i * 3^j * 5^k, how 2 work out the problem efficiently?

Post by lotoren » Mon Jan 07, 2008 12:20 pm

Recently, I met an interesting problem, I don't know whether VOJ has a similar problem.

V = 2^i * 3^j * 5^k
i, j, k all belong to natural number, i.e. , 0, 1, 2...
so, V can be 1, 2, 3, 4, 5, 6, 8, 9, 10,..... in ascending order.
Input is n, which represents the order number of V
Output is the value of V.

Sample Input
7
Sample Output
8
=============================================

Well, I've got an idea which is simple but has low efficiency.
The benefit of this idea is no need to consider the ascending order, but
there're so many invalid numbers need to be checked, such as 7 11 13
17 19...
So I wonder if there's a rule, by which V varies in ascending order with
i,j,k. Then we can only consider i, j, k, and n, without invalid V values.

Code: Select all

int main(void)
{
	int N;
	while(scanf("%d", &N)){
		if(N <= 0) continue;
		int v, p, temp;
		v = 1; p = 1;
		while(p < N){
			v++;
			temp = v;
			while(temp % 2 == 0) temp /= 2;
			if(temp == 1) { p++; continue;}
			while(temp % 3 == 0) temp /= 3;
			if(temp == 1) { p++; continue;}
			while(temp % 5 == 0) temp /= 5;
			if(temp == 1) { p++; continue;}
		}
		printf("%d\n", v);
	}
	return 0;
}
Has anybody got a smart idea, thanks!

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Jan 07, 2008 2:02 pm

Here is a similar problem
136-Ugly Numbers.

A better way of doing it is..

Let a1 a2 a3 ... an be the first n such numbers.
Then the (n+1)th number has to be the min( ai*2, aj*3, ak*5) where 1 <= i,j,k <=n and ai*2, aj*3 and ak*5 are the smallest numbers just greater than an.

Or you can generate all the numbers recursively, provided you know the upper limit of the Nth value.

maxdiver
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

Post by maxdiver » Mon Jan 07, 2008 10:34 pm

This common method is known as "moving pointers" method.
(Excuse me for my bad english :) )

lotoren
New poster
Posts: 6
Joined: Sun Dec 23, 2007 11:11 am
Location: China

Post by lotoren » Tue Jan 08, 2008 9:19 am

sohel, thank u very much, u enlightened me:)

I use bisearch to find the first one in a1-an
which larger than an/2, supposing it's ai
which larger than an/3, supposing it's aj
which larger than an/5, supposing it's ak

then an+1 is min{2*ai, 3*aj, 5*ak}

rover___
New poster
Posts: 2
Joined: Sun Apr 27, 2008 4:06 am

Re: V = 2^i * 3^j * 5^k, how 2 work out the problem efficiently?

Post by rover___ » Sun Apr 27, 2008 9:33 am

think about i+j+k=C
let C=1,2,3,...
for C=1,
(I,J,K)=(1,0,0),(0,1,0),(0,0,1)
then C=2,
(I,J,K)=(1,1,0),(1,0,1),(0,1,1),(2,0,0),(0,2,0)),(0,0,2)
sort above sequence ,and go on.C=3

rover___
New poster
Posts: 2
Joined: Sun Apr 27, 2008 4:06 am

Re: V = 2^i * 3^j * 5^k, how 2 work out the problem efficiently?

Post by rover___ » Sun Apr 27, 2008 9:38 am

sorry,my answer is wrong.
listen the others...

wasifhossain
New poster
Posts: 3
Joined: Tue Apr 28, 2009 7:26 pm

Re:

Post by wasifhossain » Tue Dec 27, 2011 7:45 pm

lotoren wrote:sohel, thank u very much, u enlightened me:)

I use bisearch to find the first one in a1-an
which larger than an/2, supposing it's ai
which larger than an/3, supposing it's aj
which larger than an/5, supposing it's ak

then an+1 is min{2*ai, 3*aj, 5*ak}
I give thanks to lotoren and recursively to Sohel bhai.

purple45
New poster
Posts: 1
Joined: Tue Mar 10, 2015 12:16 pm

Re: V = 2^i * 3^j * 5^k, how 2 work out the problem efficien

Post by purple45 » Tue Mar 10, 2015 1:33 pm

Then the (n+1)th number has to be the min( ai*2, aj*3, ak*5) where 1 <= i,j,k <=n and ai*2, aj*3 and ak*5 are the smallest numbers just greater than an. ???

Post Reply

Return to “Algorithms”