Dare2Solve
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.
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.
n
is not equal to 1:
n
is even, divide it by 2.n
is odd, decide whether to increment or decrement based on its value and the least significant bits.O(log n)
, as the number of bits in n
determines how many operations we perform.
O(1)
, since only a few variables are used to track the state.
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;
}
};
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
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;
}
}
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;
};