java recursive problem

take for example if n = 112 the smallest = 3.
apply (1) 2 times u get 28
apply (2) 1 time u get 12
apply (1) 2 times u get 3

if n = 48 then smallest = 1
apply (2) 1 time u get 16
apply (1) 4 times u get 1

Quote:

Original post by Anonymous Poster Quote: 2)If n is divisible by 3 or 4,he can substract n%10+(n/10)%10 Is being divisible by 4 any different than being even? I don't see how you can reconcile this with the first rule. Also, (n/10)%10 is always going to be 0 if n is an integer. So you may as well make this rule simply by n%10.

If it is divisible by 4, then (I think), you might apply any of the two rules. If it is divisible by 20 or 30 (divisible by 2, 3 and 5 or 2, 4 and 5), then you might apply any rule you want.

Also, (n/10)%10 has no reason to be 0. Take 120 for example. 120/10 = 12, 12%10 = 2... (n*10)%10 is always 0 (with a multiplication).

n%10 + (n/10)%10 is the sum of the two last digits of the number written in base 10. So if n=142, the value is 4+2=6

Quote:

Note that f(z) is the same regardless of how you arrived at z (hint: use dynamic programming).

Yes, that's a good idea... But the 3 rules seem to make the number small very quickly. So I'm pretty sure that computing f(z) for any z from 0 to n is very time consumming.
The basic recursive idea would be

f(z) = min(f(apply_rule_1(z)), f(apply_rule_2(z)), f(apply_rule_3(z), z). (apply a rule only if possible of course).

The bad thing with that is that is may recompute several times the same f(z). So you could just store the result, and compute f(z) only if it has not already been computed.

Something like

int computed[n+1]; //init all values to -1int f(int z){  if(computed[z] >= 0)    return computed[z];  int min = z;  int after_rule;  if(can_apply_rule_1(z) &&    (after_rule = f(apply_rule_1(z)))<min)    min = after_rule;  if(can_apply_rule_2(z) &&    (after_rule = f(apply_rule_2(z)))<min)    min = after_rule;  if(can_apply_rule_3(z) &&    (after_rule = f(apply_rule_3(z)))<min)    min = after_rule;  return computed[z] = min;}

:) interesting, a click on profile suggests your posts Mr Ryonckc2004 are made multiples of 7 days apart, and in general are toy-java problems.

would it be fair to guess that Java class is on a Tuesday