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

[lotoren]

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!

[sohel]

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]

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

[lotoren]

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___]

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___]

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

[wasifhossain]

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]

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