Question

2571. 将整数减少到零需要的最少操作数

English Version

题目描述

给你一个正整数 n ，你可以执行下述操作 任意 次：

• n 加上或减去 2 的某个 幂

返回使 n 等于 0 需要执行的 最少 操作数。

如果 x == 2i 且其中 i >= 0 ，则数字 x 是 2 的幂。

 

示例 1：

输入：n = 39
输出：3
解释：我们可以执行下述操作：
- n 加上 20 = 1 ，得到 n = 40 。
- n 减去 23 = 8 ，得到 n = 32 。
- n 减去 25 = 32 ，得到 n = 0 。
可以证明使 n 等于 0 需要执行的最少操作数是 3 。

示例 2：

输入：n = 54
输出：3
解释：我们可以执行下述操作：
- n 加上 21 = 2 ，得到 n = 56 。
- n 加上 23 = 8 ，得到 n = 64 。
- n 减去 26 = 64 ，得到 n = 0 。
使 n 等于 0 需要执行的最少操作数是 3 。 

 

提示：

• 1 <= n <= 105

解法

方法一：贪心 + 位运算

我们将整数 $n$ 转换为二进制，从最低位开始：

• 如果当前位为 $1$，我们就累加当前连续的 $1$ 的个数；
• 如果当前位为 $0$，我们就判断当前连续的 $1$ 的个数是否超过 $0$。如果是，判断当前连续的 $1$ 的个数是否为 $1$，如果是，说明我们通过一次操作可以消除 $1$；如果大于 $1$，说明我们通过一次操作，可以把连续的 $1$ 的个数减少到 $1$。

最后，我们还需要判断当前连续的 $1$ 的个数是否为 $1$，如果是，说明我们通过一次操作可以消除 $1$；如果大于 $1$，我们通过两次操作，可以把连续的 $1$ 的消除。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。其中 $n$ 为题目给定的整数。

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