Problem from Bloomberg Codecon qualifier

Revision en3, by alwerty, 2018-11-13 02:02:00

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English alwerty 2018-11-13 02:02:00 33 Tiny change: '~~\n\nint N;\n\nint so' -> '~~\n\nint so'
en2 English alwerty 2018-11-13 01:11:46 0 (published)
en1 English alwerty 2018-11-13 01:05:50 1001 Initial revision (saved to drafts)