MediumNo. 0397

Integer Replacement — LeetCode 397 Python Solution

Topics
Greedy, Bit Manipulation, Memoization, Dynamic Programming
Reading time
2 min

The problem

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.

Example

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

Python solution

PythonSolution
class Solution:
    def integerReplacement(self, n: int) -> int:
        ans = 0
        while n != 1:
            if (n & 1) == 0:
                n >>= 1
            elif n != 3 and (n & 3) == 3:
                n += 1
            else:
                n -= 1
            ans += 1
        return ans

Complexity

Time
O(n·m) (typical)
Space · auxiliary
O(n·m)or optimized

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 397. Integer Replacement is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 397. Integer Replacement?

LeetCode 397. Integer Replacement is rated Medium on LeetCode.

What topics does LeetCode 397. Integer Replacement cover?

LeetCode 397. Integer Replacement is tagged Greedy, Bit Manipulation, Memoization and Dynamic Programming on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.