LeetCode 397: Integer Replacement Solution in Python – A Step-by-Step Guide

What Is LeetCode 397: Integer Replacement?

In LeetCode 397: Integer Replacement, you’re given a positive integer n, and you need to find the minimum number of operations to turn it into 1. The operations are:

• If n is even, divide it by 2 (n = n / 2).
• If n is odd, either add 1 (n = n + 1) or subtract 1 (n = n - 1).

You keep going until n becomes 1, counting each step. For example, with n = 7, you could go 7 → 6 → 3 → 2 → 1 (4 steps) or 7 → 8 → 4 → 2 → 1 (4 steps). The challenge is picking the path with the least moves.

Problem Statement

• Input: A positive integer n.
• Output: The minimum number of operations to reduce n to 1.
• Rules:
• Even: divide by 2.
• Odd: add 1 or subtract 1.

Constraints

• 1 <= n <= 2³¹ - 1 (fits in a 32-bit integer).

Examples

• Input: n = 8
• Output: 3 (8 → 4 → 2 → 1).
• Input: n = 7
• Output: 4 (7 → 6 → 3 → 2 → 1 or 7 → 8 → 4 → 2 → 1).
• Input: n = 4
• Output: 2 (4 → 2 → 1).

Understanding the Problem: Shrinking to 1

To solve LeetCode 397: Integer Replacement in Python, we need a way to transform n into 1 with the fewest steps, choosing between division or tweaking by 1. A simple idea might be to try every possible path—but with big numbers, that’s way too many options! Instead, we’ll use:

• Best Solution (Greedy with Bit Manipulation): O(log n) time, O(1) space—uses number patterns for speed.
• Alternative Solution (Recursive DP): O(log n) time, O(log n) space—builds a memory of steps.

Let’s dive into the greedy bit manipulation solution with a clear, step-by-step explanation.

Best Solution: Greedy with Bit Manipulation

Why This Is the Best Solution

The greedy approach with bit manipulation is the top pick because it’s fast—O(log n) time, O(1) space—and smart. It looks at the number’s binary form (its 1s and 0s) to decide whether adding or subtracting 1 gets us to 1 faster, then divides by 2 when possible. It’s like having a map of the number’s bits to guide us straight to the finish line!

How It Works

Let’s think of the number as a pile of blocks we’re trying to shrink:

• Step 1: Check if Even or Odd:
• If even (ends in 0 in binary), divide by 2—cuts the pile in half.
• If odd (ends in 1), choose +1 or -1.
• Step 2: Decide for Odd Numbers:
• Look at the last two bits:
• If ...01 (e.g., 3 = 11), subtract 1 (3 → 2).
• If ...11 (e.g., 7 = 111), add 1 (7 → 8), unless it’s 3 (special case).
• Why? Adding 1 to ...11 often makes it ...00 (e.g., 7 → 8), which divides by 2 twice fast. Subtracting 1 from ...01 makes it even quicker.
• Step 3: Keep Going:
• After each move, check the new number, repeat until 1.
• Step 4: Count Steps:
• Every divide or add/subtract is 1 step.
• Step 5: Why This Works:
• Dividing by 2 reduces the number fastest (like halving the pile).
• For odds, bit patterns show which choice (+1 or -1) leads to more divisions sooner.
• Special case: 3 goes to 2 (not 4) because 2 → 1 is one step, while 4 → 2 → 1 is two.

It’s like a number-shrinking game with a bit-based strategy!

Step-by-Step Example

Example: n = 7

• Start: 7 (binary 111):
• Odd, last two bits are 11.
• Add 1: 7 → 8 (1000), steps = 1.
• 8 (1000):
• Even, divide: 8 → 4 (100), steps = 2.
• 4 (100):
• Even, divide: 4 → 2 (10), steps = 3.
• 2 (10):
• Even, divide: 2 → 1 (1), steps = 4.
• Result: 4 steps.

Example: n = 3

• Start: 3 (11):
• Odd, but it’s 3—special case.
• Subtract 1: 3 → 2 (10), steps = 1.
• 2 (10):
• Even, divide: 2 → 1 (1), steps = 2.
• Result: 2 steps.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every move:

class Solution:
    def integerReplacement(self, n: int) -> int:
        steps = 0
        # Work with n as a long integer to avoid overflow
        num = n

        # Keep going until we hit 1
        while num > 1:
            # Step 1: If even, divide by 2
            if num % 2 == 0:
                num = num // 2
                steps += 1
            # Step 2: If odd, check bits to decide
            else:
                # Special case: 3 goes to 2
                if num == 3:
                    num = 2
                    steps += 1
                # Look at last two bits
                elif num & 3 == 3:  # Ends in 11 (e.g., 7 = 111)
                    num += 1
                    steps += 1
                else:  # Ends in 01 (e.g., 5 = 101)
                    num -= 1
                    steps += 1

        return steps

• Line 4-5: Start with 0 steps, use num to track the number (helps with big values).
• Line 8-22: Main loop until num is 1:
• Line 9-11: If even (num % 2 == 0), divide by 2, add 1 step. E.g., 8 → 4.
• Line 13-22: If odd:
• Line 14-16: If 3, subtract 1 (3 → 2), add 1 step—shortest path.
• Line 17-19: Check last two bits with num & 3 (bitwise AND):
• If 3 (11 in binary, e.g., 7), add 1 (7 → 8), add 1 step.
• Line 20-22: Otherwise (e.g., 01 like 5), subtract 1 (5 → 4), add 1 step.
• Line 24: Return total steps.
• Time Complexity: O(log n)—each divide halves the number, odd steps are quick.
• Space Complexity: O(1)—just a couple of variables.

This is like a bit-guided shortcut to 1!

Alternative Solution: Recursive Dynamic Programming

Why an Alternative Approach?

The recursive dynamic programming (DP) method builds a memory of steps for each number, trying both +1 and -1 for odds. It’s O(log n) time with O(log n) space—slower and heavier than greedy but shows a different way to think about it. It’s like keeping a notebook of every number’s best path to 1!

How It Works

Picture it as a tree of choices:

• Step 1: If even, divide by 2.
• Step 2: If odd, try both +1 and -1, pick the shorter path.
• Step 3: Use a dictionary to remember results.
• Step 4: Build up to the answer recursively.

Step-by-Step Example

Example: n = 7

• 7: Odd, try 8 (+1) or 6 (-1).
• 8 → 4 → 2 → 1 (3 steps) + 1 = 4.
• 6 → 3 → 2 → 1 (3 steps) + 1 = 4.
• Result: 4 steps.

Code for Recursive DP Approach

class Solution:
    def integerReplacement(self, n: int) -> int:
        # Memo to store steps for each number
        memo = {}

        def dp(num):
            if num == 1:
                return 0
            if num in memo:
                return memo[num]

            # Even: divide by 2
            if num % 2 == 0:
                memo[num] = 1 + dp(num // 2)
            # Odd: try both +1 and -1
            else:
                memo[num] = 1 + min(dp(num + 1), dp(num - 1))
            return memo[num]

        return dp(n)

• Time Complexity: O(log n)—recursion depth, memoized.
• Space Complexity: O(log n)—memo dictionary.

It’s a memory-assisted journey to 1!

Comparing the Two Solutions

• Greedy with Bits (Best):
• Pros: O(log n), O(1), fast and light.
• Cons: Bit logic to learn.
• Recursive DP (Alternative):
• Pros: O(log n), O(log n), clear choices.
• Cons: More space, slower.

Greedy wins.

Additional Examples and Edge Cases

• 1: 0 (already 1).
• 15: 5 (15 → 16 → 8 → 4 → 2 → 1).
• 2³¹ - 1: Greedy handles big numbers.

Greedy nails them.

Complexity Breakdown

• Greedy with Bits: Time O(log n), Space O(1).
• Recursive DP: Time O(log n), Space O(log n).

Greedy’s the speed king.

Key Takeaways

• Greedy Bits: Follow the pattern!
• Recursive DP: Remember the path!
• Numbers: Bits are cool.
• Python Tip: Loops and dicts rule—see [Python Basics](/python/basics).

Final Thoughts: Shrink to Win

LeetCode 397: Integer Replacement in Python is a number-shrinking adventure. Greedy bit manipulation races to 1, while recursive DP maps it out. Want more number fun? Try LeetCode 204: Count Primes or LeetCode 279: Perfect Squares. Ready to replace? Head to Solve LeetCode 397 on LeetCode and shrink that number today!