397. Integer Replacement

Description

The problem is to find the minimum number of steps required to reduce a given integer n to 1. In each step, if n is even, you divide it by 2. If n is odd, you can either increment or decrement n by 1.

Intuition

For even numbers, the division by 2 is straightforward. For odd numbers, it’s less clear whether we should increment or decrement. Through experimentation, it becomes evident that we should decrement if n is 3 or if n >> 1 is even. Otherwise, we should increment to reduce the number of steps.

Approach

1. Initialize a count to track the number of steps.
2. While n is not equal to 1: - If n is even, divide it by 2. - If n is odd, decide whether to increment or decrement based on its value and the least significant bits.
3. Return the total count of steps taken.

Complexity

Time Complexity:

O(log n), as the number of bits in n determines how many operations we perform.

Space Complexity:

O(1), since only a few variables are used to track the state.

Code

C++

class Solution {
public:
    int integerReplacement(int n) {
        int count = 0;
        long num = n; // Use long to avoid overflow issues with large integers

        while (num != 1) {
            if ((num & 1) == 0) {
                num >>= 1;
            } else {
                if (num == 3 || ((num >> 1) & 1) == 0) {
                    num--;
                } else {
                    num++;
                }
            }
            count++;
        }
        return count;
    }
};

Python

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

Java

class Solution {
    public int integerReplacement(int n) {
        int count = 0;
        long num = n; // Use long to avoid overflow issues with large integers

        while (num != 1) {
            if ((num & 1) == 0) {
                num >>= 1;
            } else {
                if (num == 3 || ((num >> 1) & 1) == 0) {
                    num--;
                } else {
                    num++;
                }
            }
            count++;
        }
        return count;
    }
}

JavaScript

var integerReplacement = function (n) {
    let count = 0;

    while (n !== 1) {
        if (n < 0) n = -n;
        if ((n & 1) === 0) {
            n = n >> 1;

        } else {
            
            if (n === 3 || ((n >> 1) & 1) === 0) {
                n--;
            } else {
                n++;
            }
        }
        count++;
    }
    return count;
};