Integer Replacement Solution in Python

Problem Description

Ah, the classic Integer Replacement problem! Imagine you’re at a party, and you’ve got a number, let’s say 8. You want to make it smaller, but you can only do it in two ways: either divide it by 2 (because who doesn’t love halving their problems?) or, if it’s odd, you can either add or subtract 1. It’s like trying to decide whether to take the stairs or the elevator—sometimes you just have to take a step back (or forward) to get to your destination!

In this problem, you need to find the minimum number of operations required to reduce a given integer n to 1. Sounds simple, right? Well, it’s a bit like trying to get your cat to take a bath—there are many ways to do it, but most of them end in chaos!

Code Solution


class Solution:
    def integerReplacement(self, n: int) -> int:
        ans = 0

        while n > 1:
            if n % 2 == 0:  # `n` ends in 0.
                n >>= 1
            elif n == 3 or (n >> 1 & 1) == 0:  # `n` = 3 or ends in 0b01.
                n -= 1
            else:  # `n` ends in 0b11.
                n += 1
            ans += 1

        return ans

Approach

The approach taken in this solution is quite straightforward. The algorithm uses a while loop to repeatedly check the value of n. If n is even, it divides it by 2. If n is odd, it checks if it’s 3 or if the next number is even, and then decides whether to add or subtract 1. Each operation increments the answer counter until n reaches 1. It’s like playing a game of hot potato, but instead of passing the potato, you’re just trying to get rid of it!

Time and Space Complexity

Time Complexity

O(log n) – The number of operations is logarithmic in relation to n because we are halving the number when it is even.

Space Complexity

O(1) – We are using a constant amount of space regardless of the input size.

Real-World Example

Think of the Integer Replacement problem like trying to reduce your monthly expenses. You can either cut down on your spending (divide by 2) or make small adjustments (add or subtract 1). The goal is to get your expenses down to zero (or in this case, 1). Just like in life, sometimes you have to make tough choices to reach your goal!