alwerty's blog

By alwerty, history, 6 years 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?

Full text and comments »

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