alwerty's blog

By alwerty, history, 13 months ago, In English,

I tried all day to solve this problem:

Bring an integer N to 1 doing one of these operations each step: N /= 3; N /= 2; N -= 1;

1 <= N <= 1e9

output = minimum number of steps.

This is the function I wrote:


int solve(int n) { if (n == 1) return 0; if (n == 2) return 1; if (n % 3 == 0) { if (n % 2 == 0) return solve(n / 3) + 1; else return min(solve(n / 3), solve((n - 1) / 2) + 1) + 1; } if (n % 2 == 0) { if ((n - 1) % 3 == 0) return min(solve((n - 1) / 3) + 1, solve(n / 2)) + 1; else return min(solve((n - 2) / 3) + 2, solve(n / 2)) + 1; } if ((n - 1) % 3 == 0) return min(solve((n - 1) / 3), solve((n - 1) / 2)) + 2; return min(solve((n - 2) / 3) + 1, solve((n - 1) / 2)) + 2 ; }

I think the complexity of my solution is linear and the answer it gives should be correct but I'm not sure.

Can you help me find the best solution?

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it