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

Moderator: Board moderators

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

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!
lotoren
New poster

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

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.

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

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

Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov

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}
lotoren
New poster

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

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

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?

listen the others...
rover___
New poster

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

### Re:

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.
wasifhossain
New poster

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