🎨 Try our Free AI Image Generation Feature

397. Integer Replacement

avatar
Dare2Solve

10 months ago

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;
};