1611. Minimum One Bit Operations to Make Integers Zero

HardBit ManipulationMemoizationDynamic Programming

Problem Description

Given an integer n, the task is to calculate the minimum number of operations required to reduce it to 0. The operations permitted are as follows:

Flip the rightmost (0th) bit in the binary representation of n.
Flip the ith bit if and only if the (i-1)th bit is 1, and all bits from the (i-2)th down to the 0th bit are 0.

It's a binary operation challenge that requires an understanding of bit manipulation and binary representation of numbers.

Intuition

The intuition behind the solution lies in recognizing a pattern that occurs with the binary representation of the numbers while performing the given operations. Upon iteratively flipping bits according to the rules, we can observe that the problem resembles the Gray code to binary conversion.

In Gray code, each subsequent number differs from the preceding one in only one bit. Similarly, while flipping the bits as per the given rules, when we reach zero, we would have effectively constructed a series of numbers in reverse Gray code order starting at n.

Therefore, the minimum number of operations required to reduce n to zero would be the unique number that we would get if we were to flip bits from n to zero following the rules. This number is obtained by performing a bitwise XOR (^) between the current answer and the right-shifted (>>) version of n. We continue this process until n becomes zero, at which point our ans would contain the minimum number of operations required.

To add further clarification, the bitwise XOR operation here effectively keeps track of flipping the bits, as XORing a bit with 1 changes it, and XORing it with 0 leaves it unchanged. The right shift operation simulates the dependency of flipping a given bit based on the state of its right neighbor, as described by the rules.

Learn more about Memoization and Dynamic Programming patterns.

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

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

O(1)O(n)O(n!)O(n^n)

I don’t know

Solution Approach

The solution uses a simple while loop and bitwise operations to solve the problem with no need for additional data structures. The pattern used is akin to the iterative bit flipping carried out in a Gray code to binary conversion. Here's a step-by-step breakdown of the solution:

Initialize the ans variable to 0. This variable will accumulate the number of operations performed.
Enter a while loop that continues as long as n is not 0.
Within the loop, perform a bitwise XOR between ans and n. This operation updates ans with the accumulated result of the "flips" so far. The XOR operation is perfectly suited for this as it effectively toggles the bits—flipping a 1 to 0 or a 0 to 1—based on whether there is a 1 in the corresponding position of n (analogous to performing the flip operation).
- The expression ans ^= n means ans = ans ^ n, where ^ is the bitwise XOR operator.
Perform a right bitwise shift on n using n >>= 1. This operation prepares the next bit in n to be XORed with ans in the next iteration of the loop by moving all bits one place to the right. It is effectively checking whether the current bit should be flipped or not based on the rule of flipping bit i if bit (i-1) is set to 1 and all lesser significant bits are 0. The right shift moves the bits down such that each "next" bit becomes the "current" bit for the next operation.
The loop continues, flipping bits one by one until n is reduced to 0.
The final value of ans after the loop terminates is the total number of operations required. Return ans.

In this implementation, there is no need for complex algorithms or large data structures as the problem's constraints and behavior allow for a more direct and efficient approach using bitwise manipulation only.

The performance of this algorithm is determined by the number of bits in n, which is O(log n) since each iteration of the while loop shifts n one bit to the right until it becomes zero.

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

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

TrueFalse

I don’t know

Example Walkthrough

Let's illustrate the solution approach using a small example. Suppose we are given the integer n = 6.

We need to determine the minimum number of operations required to reduce it to 0 following the rules provided.

First, let's look at the binary representation of n: n = 6 in binary is 110.

Now we will apply the operations defined in the problem description while keeping track of the number of operations.

Initialize ans to 0.
Begin the while loop since n is not yet 0.

a. Perform ans ^= n:
- ans = 0
- n in binary is 110
- ans ^= n gives us 110, so now ans is 110.
b. Perform n >>= 1 (right shift n):
- n after the shift is 11 in binary (which is 3 in decimal).
The next iteration starts as n is still not 0.

a. Perform ans ^= n:
- ans = 110 in binary.
- n is now 11 in binary.
- ans ^= n gives us 101, so now ans is 101.
b. Perform n >>= 1:
- n after the shift is 1 in binary (which is 1 in decimal).
Proceed to the next iteration since n is not 0.

a. Perform ans ^= n:
- ans = 101 in binary.
- n is 1 in binary.
- ans ^= n gives us 100, so now ans is 100.
b. Perform n >>= 1:
- n after the shift is 0 in binary (which is 0 in decimal).

At this point, n has become 0, so the loop terminates. The ans, which represents the minimum number of operations required to reduce n to 0, is 100 in binary. This is 4 in decimal.

Therefore, the minimum number of operations required to reduce 6 to 0 is 4.

The steps taken illustrate the incremental changes in n and ans. Each loop iteration performs one or two operations complying with the rules: either flipping the rightmost bit or shifting right and preparing for the next bit flip.

The final binary number 100 represents a count of every flip that happened from 6 to 0. Using this approach, for any given integer n, one can find the minimum number of operations required to reduce it to 0.

Solution Implementation

1class Solution:
2    def minimumOneBitOperations(self, n: int) -> int:
3        # Initialize the answer to zero.
4        result = 0
5      
6        # Continue the loop until n becomes zero.
7        while n:
8            # Apply bitwise XOR to the current result and n.
9            # This is part of the process to find the minimum operations.
10            result ^= n
11          
12            # Right shift the bits of n by one position.
13            # This operation reduces the number being processed bit by bit.
14            n >>= 1
15      
16        # Return the computed result.
17        return result
18

1class Solution {
2
3    // Function to calculate the minimum number of operations required
4    // to transform the integer 'n' into zero by flipping exactly one bit in a binary representation
5    public int minimumOneBitOperations(int n) {
6        int result = 0; // Initialize the result variable to store the minimum operations
7
8        // Iterate until n becomes zero
9        while (n > 0) {
10            // Use XOR to keep track of bit operations, exploiting the 
11            // property that going down to zero with one-bit operations can be seen as toggling bits
12            result ^= n;
13
14            // Right shift 'n' by 1 to divide it by 2, moving to the next bit
15            n >>= 1;
16        }
17      
18        // Return the calculated result
19        return result;
20    }
21}
22

1class Solution {
2public:
3    // Function to calculate the minimum number of operations required to
4    // reduce the number 'n' to zero, where each operation consists of flipping
5    // exactly one bit, and the operation must change the value of the integer.
6    int minimumOneBitOperations(int n) {
7        int result = 0; // Initialize result to 0, which will hold the final answer.
8      
9        // Loop until 'n' is reduced to zero. In each iteration, 'n' is right shifted
10        // by one bit (n >>= 1), effectively dividing 'n' by 2 and discarding the least significant bit.
11        while (n > 0) {
12            // Perform bitwise XOR between the current result and 'n' and store the result back.
13            // This progressively calculates the necessary bit-flips.
14            result ^= n;
15          
16            // Right shift 'n' by one bit to examine and process the next bit in the next iteration.
17            n >>= 1;
18        }
19      
20        // Return the accumulated result, which represents the minimum one bit operations
21        // necessary to reduce the binary number to zero.
22        return result;
23    }
24};
25

1// Function to find the minimum number of operations to transform a given number into zero
2// by toggling the least significant bit (rightmost bit) of the number.
3function minimumOneBitOperations(n: number): number {
4    // Initialize the answer to zero.
5    let answer = 0;
6  
7    // Loop until the number n is greater than zero.
8    while (n > 0) {
9        // Apply bitwise XOR between the answer and the current number
10        // to accumulate the effect of one-bit operations.
11        answer ^= n;
12      
13        // Right shift the number by one to eliminate the least significant bit
14        // and proceed with the next bit in the next iteration.
15        n >>= 1;
16    }
17  
18    // Return the total number of operations needed.
19    return answer;
20}
21

Not Sure What to Study? Take the 2-min Quiz：

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

O(1)O(log n)O(n)O(n logn)

I don’t know

Time and Space Complexity

The given Python function minimumOneBitOperations consists of a while loop that runs as long as the input integer n is non-zero. On each iteration, the current value of n is XORed with ans, and then n is right-shifted by 1.

Time Complexity

The time complexity of the algorithm depends on the number of bits in the binary representation of the integer n. If n has a total of b bits, the loop iterates at most b times, since with each shift, one bit is removed from n. Thus, the time complexity is O(b), which can also be considered O(log n) since the number of bits b is proportional to the logarithm of the number n.

Space Complexity

The space complexity of the algorithm is O(1). This is because the algorithm uses a fixed amount of space: a single integer variable ans. The space required does not change with the size of the input n, indicating constant space complexity.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?

Fast-slow pointersTwo pointers moving in opposite directionSliding windowPrefix sum

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1611. Minimum One Bit Operations to Make Integers Zero

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings