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?