Skip to content

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

Thinking

Each step adds or subtracts a power of two. Clearing bits independently costs one step per one, but a run of ones can be removed by adding the next power and subtracting, which is cheaper.

Scan runs from the low bit. A singleton is subtracted in one step; a longer run is collapsed by adding the next bit, leaving a carry of one. A leftover run at the end costs one step if its length is \(1\), otherwise two.

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.

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

Comments