Given an integer n, you must transform it into 0 using the following operations any number of times:
0th) bit in the binary representation of n.ith bit in the binary representation of n if the (i-1)th bit is set to 1 and the (i-2)th through 0th bits are set to 0.Return the minimum number of operations to transform n into 0.
Example 1:
Input: n = 3 Output: 2 Explanation: The binary representation of 3 is "11". "11" -> "01" with the 2nd operation since the 0th bit is 1. "01" -> "00" with the 1st operation.
Example 2:
Input: n = 6 Output: 4 Explanation: The binary representation of 6 is "110". "110" -> "010" with the 2nd operation since the 1st bit is 1 and 0th through 0th bits are 0. "010" -> "011" with the 1st operation. "011" -> "001" with the 2nd operation since the 0th bit is 1. "001" -> "000" with the 1st operation.
Constraints:
0 <= n <= 109The idea is to use a recursive function to determine the minimum number of operations needed to reduce the given number n to 0. Consider each bit change step as a recursive call, effectively exploring the tree of possibilities until we reach 0.
We need to account for the operation rules defined in the problem, particularly handling the change in the i-th bit when needed.
This function computes the recursive solution. It checks the highest set bit and recurses by flipping the bit using XOR and adjusting the metric accordingly. The base case is when n is 0.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n), where n is the input size.
Space Complexity: O(log n), due to the recursion stack.
This approach removes recursion and implements the bit operations iteratively. The key step involves simulating the recursive logic using a while loop and maintaining a transformation count.
The iterative loop continuously XORs res with current num and shifts num right, mimicking recursive pattern iteratively.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(log n), where n is the input size. |
| Iterative Approach Using Bit Manipulation | Time Complexity: O(log n) |
Number of 1 Bits - Leetcode 191 - Python • NeetCode • 155,494 views views
Watch 9 more video solutions →Practice Minimum One Bit Operations to Make Integers Zero with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor