跳转至

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

题目描述

给你一个正整数 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$ 为题目给定的整数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
}

评论