Welcome to Subscribe On Youtube
2571. Minimum Operations to Reduce an Integer to 0
Description
You are given a positive integer n
, you can do the following operation any number of times:
 Add or subtract a power of
2
fromn
.
Return the minimum number of operations to make n
equal to 0
.
A number x
is power of 2
if x == 2^{i}
where i >= 0
.
Example 1:
Input: n = 39 Output: 3 Explanation: We can do the following operations:  Add 2^{0} = 1 to n, so now n = 40.  Subtract 2^{3} = 8 from n, so now n = 32.  Subtract 2^{5} = 32 from n, so now n = 0. It can be shown that 3 is the minimum number of operations we need to make n equal to 0.
Example 2:
Input: n = 54 Output: 3 Explanation: We can do the following operations:  Add 2^{1} = 2 to n, so now n = 56.  Add 2^{3} = 8 to n, so now n = 64.  Subtract 2^{6} = 64 from n, so now n = 0. So the minimum number of operations is 3.
Constraints:
1 <= n <= 10^{5}
Solutions
Solution 1: Greedy + Bitwise Operation
We convert the integer $n$ to binary, starting from the lowest bit:
 If the current bit is 1, we accumulate the current number of consecutive 1s;
 If the current bit is 0, we check whether the current number of consecutive 1s is greater than 0. If it is, we check whether the current number of consecutive 1s is 1. If it is, it means that we can eliminate 1 through one operation; if it is greater than 1, it means that we can reduce the number of consecutive 1s to 1 through one operation.
Finally, we also need to check whether the current number of consecutive 1s is 1. If it is, it means that we can eliminate 1 through one operation; if it is greater than 1, we can eliminate the consecutive 1s through two operations.
The time complexity is $O(\log n)$, and the space complexity is $O(1)$. Here, $n$ is the given integer in the problem.

class Solution { public int minOperations(int n) { int ans = 0, cnt = 0; for (; n > 0; n >>= 1) { if ((n & 1) == 1) { ++cnt; } else if (cnt > 0) { ++ans; cnt = cnt == 1 ? 0 : 1; } } ans += cnt == 1 ? 1 : 0; ans += cnt > 1 ? 2 : 0; return ans; } }

class Solution { public: int minOperations(int n) { int ans = 0, cnt = 0; for (; n > 0; n >>= 1) { if ((n & 1) == 1) { ++cnt; } else if (cnt > 0) { ++ans; cnt = cnt == 1 ? 0 : 1; } } ans += cnt == 1 ? 1 : 0; ans += cnt > 1 ? 2 : 0; return ans; } };

class Solution: def minOperations(self, n: int) > int: ans = cnt = 0 while n: if n & 1: cnt += 1 elif cnt: ans += 1 cnt = 0 if cnt == 1 else 1 n >>= 1 if cnt == 1: ans += 1 elif cnt > 1: ans += 2 return ans

func minOperations(n int) (ans int) { cnt := 0 for ; n > 0; n >>= 1 { if n&1 == 1 { cnt++ } else if cnt > 0 { ans++ if cnt == 1 { cnt = 0 } else { cnt = 1 } } } if cnt == 1 { ans++ } else if cnt > 1 { ans += 2 } return }

function minOperations(n: number): number { let [ans, cnt] = [0, 0]; for (; n; n >>= 1) { if (n & 1) { ++cnt; } else if (cnt) { ++ans; cnt = cnt === 1 ? 0 : 1; } } if (cnt === 1) { ++ans; } else if (cnt > 1) { ans += 2; } return ans; }