Problem from Bloomberg Codecon qualifier

Правка en2, от alwerty, 2018-11-13 01:11:46

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 min(solve(n / 3), solve(n / 2)) + 1;
        else return  min(solve(n / 3), solve(n - 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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский alwerty 2018-11-13 02:02:00 33 Tiny change: '~~\n\nint N;\n\nint so' -> '~~\n\nint so'
en2 Английский alwerty 2018-11-13 01:11:46 0 (published)
en1 Английский alwerty 2018-11-13 01:05:50 1001 Initial revision (saved to drafts)