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?