2571. Minimum Operations to Reduce an Integer to 0


Problem Description

You are given a positive integer n. The task is to transform n to 0 by repeatedly performing the following operation: add or subtract a power of 2 to/from n. The available powers of 2 range from 2^0 up to any higher power (as 2^1, 2^2, and so on). The goal is to find the minimum number of such operations required to achieve n = 0.

In simpler words, you're essentially allowed to repeatedly increase or decrease the integer n by any value that is a power of 2 (like 1, 2, 4, 8, and so on), and you need to find the least number of times you have to do this to get to 0.

Intuition

The solution involves a strategic approach rather than trying out different powers of 2 at random. We look at the binary representation of the given integer n. Since binary representation is based on powers of 2, incrementing or decrementing by powers of 2 can be visualized as flipping specific bits in the binary form.

So, we scan through the binary digits (bits) of n from least significant to most significant (from the right-hand side to the left).

  • If we encounter a 1 bit, this represents a power of 2 that we need to cancel out. We keep a running total of consecutive 1 bits because a string of 1s may be dealt with more efficiently together rather than individually.

  • When we encounter a 0 bit, this provides an opportunity to address the consecutive 1 bits encountered before it. If there's only one 1 bit, we can perform a single subtract operation to remove it. If there are multiple 1s, we can turn all but one of them into 0 by adding a power of 2 that's just higher than the string of 1s. This adds 1 to the count of subtract operations needed.

In the end, we might be left with a string of 1s at the most significant end. We'll need two operations if there are multiple 1s (add and then subtract the next higher power of 2), or just one if there's a single 1.

The algorithm hence devised is cautious; it chooses the most effective operation at each step due to its bitwise considerations, ensuring fewer total operations.

Learn more about Greedy and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

In a binary min heap, the minimum element can be found in:

Solution Approach

The Python code provided implements the algorithm through a mix of bitwise operations and a greedy approach.

Let's walk through the implementation:

  1. Initialize ans and cnt. The variable ans keeps track of the total number of operations required, and cnt counts the consecutive 1 bits in the binary representation of n.

  2. Process the binary digits of n from least significant to most significant. This is done by examining n bit by bit in a loop where the iteration involves a right shift operation n >>= 1, effectively moving to the next bit towards the left.

  3. When the current bit is 1 (checked by if n & 1), increment the cnt by 1. This is because each 1 represents a power of 2 that must be addressed.

  4. If the current bit is 0 and cnt is not zero, this indicates we have just finished processing a sequence of 1 bits. Now, determine how to handle them:

    • If cnt equals 1, increment ans by 1, as we need one operation to subtract this power of 2.
    • If cnt is more than 1, increment ans by 1 and set cnt to 1. The rationale here is that we've added a power of 2 that turns all but one of the consecutive 1 bits into 0. We're left with one last subtraction operation to perform later.
  5. After processing all bits, there may be a leftover cnt:

    • If cnt is 1, we only need one more operation, so add 1 to ans.
    • If cnt is greater than 1, we need a two-step operation where we first add and then subtract the next power of 2, hence add 2 to ans.
  6. Finally, return the accumulated result ans, which gives us the minimum number of operations needed to transform n into 0.

By leveraging bitwise operations, the solution is both efficient and straightforward. There's no need for iteration or recursion that directly considers powers of 2; instead, the solution operates implicitly on powers of 2 by manipulating binary digits, which are intrinsically linked to powers of 2.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's illustrate the solution approach using the example of n = 23. The binary representation of 23 is 10111. We will apply the solution approach step by step:

  1. Initialize ans = 0 and cnt = 0. No operations have been done yet.
  2. As n is 10111, we process from the rightmost bit to the left:
    • Bit 1 (rightmost): n & 1 is true so increment cnt to 1.
    • Bit 2: n & 1 is true so increment cnt to 2.
    • Bit 3: n & 1 is true so increment cnt to 3.
    • Bit 4: n & 1 is false, and cnt is 3. Therefore, increment ans to 1 and reset cnt to 1 (because we perform an add operation to turn the sequence 111 into 1000, which leaves one operation for later).
    • Last shift will happen, and now n becomes 2 (10 in binary), and we've processed all bits.
  3. Leftover cnt is 1 because our binary representation now starts with 1. We increment ans by 1 because a final subtract operation is needed.
  4. Finally, ans is 2 because we performed 2 operations in total: converting 10111 to 11000 (+1 operation) and then to 0 (-1 operation).

The minimum number of operations required to transform n = 23 into 0 using the solution approach is 2.

Solution Implementation

1class Solution:
2    def minOperations(self, n: int) -> int:
3        # Initialize operations count (ops) and a counter for consecutive ones (consecutive_ones).
4        ops = 0
5        consecutive_ones = 0
6      
7        # Process all bits of the integer n from right to left (LSB to MSB).
8        while n:
9            # Check if the least significant bit (LSB) is 1.
10            if n & 1:
11                # If it is, increase the counter for consecutive ones.
12                consecutive_ones += 1
13            # If it is 0 and the counter for consecutive ones is not zero.
14            elif consecutive_ones:
15                # A zero after some ones means a completed set of "10" or "110." 
16                # Operation needed to convert this set to "00" or "100".
17                ops += 1
18                # Reset the counter for consecutive ones.
19                # '1' in binary is already minimized, and for '11' we only need one operation
20                # to change it to '10' and then we 'carry the 1' so to speak.
21                consecutive_ones = 0 if consecutive_ones == 1 else 1
22          
23            # Right shift n by 1 to check the next bit.
24            n >>= 1
25      
26        # If there is a residual 1 then an operation is needed; 
27        # this could be a trailing '1' or '10' after the end of the loop.
28        if consecutive_ones == 1:
29            # Increment the operations count by 1.
30            ops += 1
31        # If there are more than 1 ones, an extra operation is needed to handle the carry.
32        elif consecutive_ones > 1:
33            # Increment the operations count by 2. This is the case for '11' in binary,
34            # where one operation is to change '11' to '10' and second operation to change
35            # '10' to '00'.
36            ops += 2
37      
38        # Return the number of operations required.
39        return ops
40
1class Solution {
2
3    public int minOperations(int num) {
4        // Initialize variables for answer and contiguous ones count
5        int operationsCount = 0;
6        int contiguousOnesCount = 0;
7
8        // Loop while number is greater than zero
9        for (; num > 0; num >>= 1) {
10            // If the least significant bit is 1
11            if ((num & 1) == 1) {
12                // Increment count of contiguous ones
13                contiguousOnesCount++;
14            } else if (contiguousOnesCount > 0) {
15                // If the least significant bit is 0 and we have seen a contiguous sequence of ones
16                operationsCount++; // Increase operations, since this is an operation to flip a zero after a one
17                // Reset/modify contiguous ones count based on the previous count
18                contiguousOnesCount = (contiguousOnesCount == 1) ? 0 : 1;
19            }
20        }
21      
22        // After processing all bits, if there is a single one left, it is a valid operation to flip it
23        operationsCount += (contiguousOnesCount == 1) ? 1 : 0;
24      
25        // If there are more than one contiguous ones left, we need two operations:
26        // one to flip the first one, and another one for the last one.
27        operationsCount += (contiguousOnesCount > 1) ? 2 : 0;
28      
29        // Return the total number of operations required
30        return operationsCount;
31    }
32}
33
1class Solution {
2public:
3    int minOperations(int n) {
4        int operations = 0; // This will hold the total number of operations required.
5        int onesCount = 0;  // This will count the number of consecutive '1' bits.
6
7        // Process each bit, starting with the least significant bit (LSB).
8        while (n > 0) {
9            if ((n & 1) == 1) {
10                // If the current bit is a '1', increment the count of consecutive ones.
11                ++onesCount;
12            } else if (onesCount > 0) {
13                // If we hit a '0' after counting some ones, we need an operation (either a flip or a move).
14                ++operations;
15              
16                // If there was only one '1', we reset the count. Otherwise, we keep the count as '1',
17                // because the bit flip would transform "01" to "10", leaving us with one '1' to move.
18                onesCount = (onesCount == 1) ? 0 : 1;
19            }
20            // Right shift the bits in n to process the next bit in the next iteration.
21            n >>= 1;
22        }
23
24        // After processing all bits, if we have one '1' left, we need one more operation to remove it.
25        if (onesCount == 1) {
26            ++operations;
27        }
28
29        // If we have more than one '1', we need an additional two operations: one for flipping and one for moving.
30        if (onesCount > 1) {
31            operations += 2;
32        }
33
34        return operations; // Return the total number of operations calculated.
35    }
36};
37
1function minOperations(n: number): number {
2    let operationsCount = 0;   // Will hold the total number of operations required.
3    let consecOnesCount = 0;    // Counter for consecutive 1's in binary representation of n.
4
5    // Iterate through the bits of n.
6    while (n !== 0) {
7        // If the least significant bit is a 1.
8        if (n & 1) {
9            consecOnesCount += 1; // We found a consecutive one, increase the counter.
10        }
11        // If it's a 0 and there are consecutive 1's counted before.
12        else if (consecOnesCount > 0) {
13            operationsCount += 1; // We need an operation to separate the consecutive 1's.
14          
15            // Reset consecOnesCount or set to 1 based on whether we had a single consecutive one or more.
16            consecOnesCount = (consecOnesCount === 1) ? 0 : 1;
17        }
18      
19        // Right shift n to check the next bit.
20        n >>= 1;
21    }
22  
23    // If there's a single 1 left.
24    if (consecOnesCount === 1) {
25        operationsCount += 1; // We'll need one more operation.
26    }
27    // If there are more than one consecutive 1's left.
28    else if (consecOnesCount > 1) {
29        operationsCount += 2; // We'll need two more operations to handle them.
30    }
31  
32    // Return the total operations count.
33    return operationsCount;
34}
35
Not Sure What to Study? Take the 2-min Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

The time complexity of the provided code is O(log n) because the primary operation within the while loop is a bitwise right shift on n, which effectively divides n by 2. The number of iterations is directly proportional to the number of bits in the binary representation of n, which is log n base 2.

The space complexity of the code is O(1) since the extra space used is constant, irrespective of the size of n. The variables ans and cnt use a fixed amount of space during the execution of the algorithm.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

A heap is a ...?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫