Question

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 from n.

Return _the minimum number of operations to make _n_ equal to _0.

A number x is power of 2 if x == 2i where i >= 0_._

 

Example 1:

Input: n = 39
Output: 3
Explanation: We can do the following operations:
- Add 20 = 1 to n, so now n = 40.
- Subtract 23 = 8 from n, so now n = 32.
- Subtract 25 = 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 21 = 2 to n, so now n = 56.
- Add 23 = 8 to n, so now n = 64.
- Subtract 26 = 64 from n, so now n = 0.
So the minimum number of operations is 3.

 

Constraints:

• 1 <= n <= 105

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:
  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

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

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