Is Integer Replacement easy or hard?

Integer Replacement is generally classified as a medium difficulty problem. The base operations are simple, but choosing the optimal action for odd numbers requires recognizing binary patterns. Many candidates initially attempt recursion before discovering the greedy bit manipulation optimization.

Integer Replacement Python/Java solution

Both Python and Java implementations typically follow the greedy rule using bit checks. Even numbers are divided by two, while odd numbers decide between increment and decrement based on n % 4 and the special case n == 3. The logic is identical across languages and runs in O(log n) time.

How to solve Integer Replacement in O(log n)?

Use a greedy rule based on the binary representation of n. If n is even, divide it by 2. If n is odd, check the last two bits: decrement when n % 4 == 1 and increment when n % 4 == 3, except for n == 3 where decrementing is optimal. This ensures the number gains more trailing zeros, enabling faster halving steps.

What is the best approach for Integer Replacement?

The greedy approach with bit manipulation is considered the best solution. It observes patterns in the binary representation of the number and chooses n+1 or n-1 based on the last two bits. This reduces the number of steps needed before repeated divisions by two. The algorithm runs in O(log n) time and uses O(1) space.

Is Integer Replacement asked at Google/Amazon/Meta?

Integer Replacement appears in interviews at large tech companies because it tests reasoning about recursion, dynamic programming, and binary representation. Variations of the problem have been reported in interviews at companies like Google and Amazon where candidates must identify the greedy bit pattern optimization.

What data structure is used in Integer Replacement?

The memoized recursive approach uses a hash map or dictionary to store previously computed results. This prevents recomputation of states when exploring n+1 and n-1 paths. The greedy solution does not require additional data structures and relies only on integer operations and bit checks.

What is the time complexity of Integer Replacement?

The optimal solutions run in O(log n) time because each operation either halves the number or converts it into a form that quickly becomes divisible by two. Since the value shrinks exponentially through division, the total number of operations grows proportional to the number of bits in n.

Description Solution Video 13:15

397. Integer Replacement

Medium37.9% acceptance4 companies

Given a positive integer n, you can apply one of the following operations:

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.

Example 1:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

Example 2:

Input: n = 7
Output: 4
Explanation: 7 -> 8 -> 4 -> 2 -> 1
or 7 -> 6 -> 3 -> 2 -> 1

Example 3:

Input: n = 4
Output: 2

Constraints:

1 <= n <= 2³¹ - 1

Asked at 4 companies

Baidu

Google Uber Amazon

Topics

13:15

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def integerReplacement(self, n: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

Your code is saved on this device.Solution