Skip to content
MediumDpAI interview only

Integer Replacement

Asked atgoogleamazonmicrosoftbloomberg

01 · Problem

Given a positive integer n, you may apply these operations repeatedly:

  • If n is even, replace n with n / 2.
  • If n is odd, replace n with either n + 1 or n - 1.

Return the minimum number of operations needed for n to become 1. If n is already 1, return 0.

02 · Examples

Example 01
Input
n = 8
Output
3

8 -> 4 -> 2 -> 1 takes 3 halvings.

Example 02
Input
n = 7
Output
4

7 -> 8 -> 4 -> 2 -> 1 takes 4 steps (7 -> 6 -> 3 -> 2 -> 1 also takes 4).

Example 03
Input
n = 15
Output
5

15 -> 16 -> 8 -> 4 -> 2 -> 1 takes 5 steps, which beats going down via 14.

03 · Constraints

  • 011 <= n <= 231 - 1
  • 02If n is even, the only move is n / 2
  • 03If n is odd, you may replace n with n + 1 or n - 1
  • 04Intermediate values may exceed 231 - 1 (use 64-bit arithmetic)

04 · Optimal complexity

Time
O(log n)
Space
O(1)
05 · Two ways to work on it

Practice it alone or rehearse it as an interview.

Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.

Start a voice interview on this problem