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

Moderator: Board moderators

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?

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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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:
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
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?

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

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

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

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

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