1611. Minimum Number of One Bit Operations to Make Integers Zero - Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Bit Manipulation - Understanding binary representation, XOR, AND, and bit shifting operations
Recursion - The base approach recursively processes each set bit from highest to lowest
Gray Codes - The elegant solution relies on understanding Gray code sequences where consecutive numbers differ by one bit

1. Math (Recursion)

Intuition

The key insight is understanding what it takes to flip the highest set bit to zero. To clear a bit at position k, we need to first set up a specific pattern where the bit at position k-1 is 1 and all lower bits are 0. This requires 2^k - 1 operations to go from 0 to that pattern. Once we have that setup, clearing the highest bit leaves us with a smaller number, and we recursively solve for that remainder. The operations alternate between adding and subtracting because each recursive step either builds toward or tears down from the target pattern.

Algorithm

Base case: if n is 0, return 0 since no operations are needed.
Find k, the highest power of 2 that is less than or equal to n. This represents the position of the highest set bit.
The number of operations to clear just the highest bit from a power of 2 is 2*k - 1 (e.g., clearing bit position 3 requires 7 operations: 2^3 * 2 - 1).
After clearing the highest bit, we have a remainder k XOR n. The operations needed for this remainder are subtracted because the setup steps overlap.
Return (k * 2) - 1 - recursiveCall(k XOR n).

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        if n == 0:
            return 0

        k = 1
        while (k << 1) <= n:
            k <<= 1

        return (k << 1) - 1 - self.minimumOneBitOperations(k ^ n)

public class Solution {
    public int minimumOneBitOperations(int n) {
        if (n == 0) {
            return 0;
        }

        int k = 1;
        while ((k << 1) <= n) {
            k <<= 1;
        }

        return (k << 1) - 1 - minimumOneBitOperations(k ^ n);
    }
}

class Solution {
public:
    int minimumOneBitOperations(int n) {
        if (n == 0) {
            return 0;
        }

        int k = 1;
        while ((k << 1) <= n) {
            k <<= 1;
        }

        return (k << 1) - 1 - minimumOneBitOperations(k ^ n);
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    minimumOneBitOperations(n) {
        if (n === 0) {
            return 0;
        }

        let k = 1;
        while (k << 1 <= n) {
            k <<= 1;
        }

        return (k << 1) - 1 - this.minimumOneBitOperations(k ^ n);
    }
}

public class Solution {
    public int MinimumOneBitOperations(int n) {
        if (n == 0) {
            return 0;
        }

        int k = 1;
        while ((k << 1) <= n) {
            k <<= 1;
        }

        return (k << 1) - 1 - MinimumOneBitOperations(k ^ n);
    }
}

class Solution {
    fun minimumOneBitOperations(n: Int): Int {
        if (n == 0) {
            return 0
        }

        var k = 1
        while ((k shl 1) <= n) {
            k = k shl 1
        }

        return (k shl 1) - 1 - minimumOneBitOperations(k xor n)
    }
}

class Solution {
    func minimumOneBitOperations(_ n: Int) -> Int {
        if n == 0 {
            return 0
        }

        var k = 1
        while (k << 1) <= n {
            k <<= 1
        }

        return (k << 1) - 1 - minimumOneBitOperations(k ^ n)
    }
}

impl Solution {
    pub fn minimum_one_bit_operations(n: i32) -> i32 {
        if n == 0 {
            return 0;
        }
        let mut k = 1;
        while (k << 1) <= n {
            k <<= 1;
        }
        (k << 1) - 1 - Self::minimum_one_bit_operations(k ^ n)
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$ for recursion stack.

2. Math (Iteration) - I

Intuition

This approach converts the recursive solution into an iterative one. We process each set bit from highest to lowest, alternating between adding and subtracting the cost. The first (highest) bit contributes positively, the next contributes negatively, and so on. This alternation happens because clearing one bit creates a pattern that partially overlaps with the work needed for the next bit.

Algorithm

Initialize res = 0, k = 2^30 (starting from the highest possible bit), and sign = 1.
While n is not zero:
- Find the highest set bit by shifting k right until k <= n.
- Add sign * (2*k - 1) to res.
- Flip the sign for the next iteration.
- Remove this bit from n using XOR: n ^= k.
Return res.

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        res = 0
        k = 1 << 30
        sign = 1

        while n:
            while k > n:
                k >>= 1

            res += (sign * ((k << 1) - 1))
            sign *= -1
            n ^= k

        return res

public class Solution {
    public int minimumOneBitOperations(int n) {
        int res = 0, k = 1 << 30, sign = 1;

        while (n != 0) {
            while (k > n) {
                k >>= 1;
            }

            res += (sign * ((k << 1) - 1));
            sign *= -1;
            n ^= k;
        }

        return res;
    }
}

class Solution {
public:
    int minimumOneBitOperations(int n) {
        int res = 0, k = 1 << 30, sign = 1;

        while (n != 0) {
            while (k > n) {
                k >>= 1;
            }

            res += sign * ((k << 1) - 1);
            sign *= -1;
            n ^= k;
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    minimumOneBitOperations(n) {
        let res = 0,
            k = 1 << 30,
            sign = 1;

        while (n !== 0) {
            while (k > n) {
                k >>= 1;
            }

            res += sign * ((k << 1) - 1);
            sign *= -1;
            n ^= k;
        }

        return res;
    }
}

public class Solution {
    public int MinimumOneBitOperations(int n) {
        int res = 0, k = 1 << 30, sign = 1;

        while (n != 0) {
            while (k > n) {
                k >>= 1;
            }

            res += (sign * ((k << 1) - 1));
            sign *= -1;
            n ^= k;
        }

        return res;
    }
}

func minimumOneBitOperations(n int) int {
    res, k, sign := 0, 1<<30, 1

    for n != 0 {
        for k > n {
            k >>= 1
        }

        res += sign * ((k << 1) - 1)
        sign *= -1
        n ^= k
    }

    return res
}

class Solution {
    fun minimumOneBitOperations(n: Int): Int {
        var num = n
        var res = 0
        var k = 1 shl 30
        var sign = 1

        while (num != 0) {
            while (k > num) {
                k = k shr 1
            }

            res += sign * ((k shl 1) - 1)
            sign *= -1
            num = num xor k
        }

        return res
    }
}

class Solution {
    func minimumOneBitOperations(_ n: Int) -> Int {
        var n = n
        var res = 0
        var k = 1 << 30
        var sign = 1

        while n != 0 {
            while k > n {
                k >>= 1
            }

            res += sign * ((k << 1) - 1)
            sign *= -1
            n ^= k
        }

        return res
    }
}

impl Solution {
    pub fn minimum_one_bit_operations(n: i32) -> i32 {
        let mut n = n;
        let mut res = 0;
        let mut k = 1 << 30;
        let mut sign = 1;

        while n != 0 {
            while k > n {
                k >>= 1;
            }
            res += sign * ((k << 1) - 1);
            sign *= -1;
            n ^= k;
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

3. Math (Iteration) - II

Intuition

This variant uses a clever bit manipulation trick. The expression n XOR (n-1) isolates the rightmost set bit and all bits to its right (as a mask of 1s). By processing bits from right to left and alternating signs, we compute the same result as the previous approaches. The absolute value at the end handles the case where the sign ends up negative.

Algorithm

Initialize res = 0 and sign = 1.
While n is not zero:
- Compute n XOR (n-1), which gives a mask from the lowest set bit to bit 0.
- Add sign * (n XOR (n-1)) to res.
- Clear the lowest set bit using n &= (n-1).
- Flip the sign.
Return the absolute value of res.

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        res, sign = 0, 1
        while n:
            res += sign * (n ^ (n - 1))
            n &= (n - 1)
            sign *= -1
        return abs(res)

public class Solution {
    public int minimumOneBitOperations(int n) {
        int res = 0, sign = 1;
        while (n != 0) {
            res += sign * (n ^ (n - 1));
            n &= (n - 1);
            sign *= -1;
        }
        return Math.abs(res);
    }
}

class Solution {
public:
    int minimumOneBitOperations(int n) {
        int res = 0, sign = 1;
        while (n != 0) {
            res += sign * (n ^ (n - 1));
            n &= (n - 1);
            sign *= -1;
        }
        return abs(res);
    }
};

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    minimumOneBitOperations(n) {
        let res = 0,
            sign = 1;
        while (n !== 0) {
            res += sign * (n ^ (n - 1));
            n &= n - 1;
            sign *= -1;
        }
        return Math.abs(res);
    }
}

public class Solution {
    public int MinimumOneBitOperations(int n) {
        int res = 0, sign = 1;
        while (n != 0) {
            res += sign * (n ^ (n - 1));
            n &= (n - 1);
            sign *= -1;
        }
        return Math.Abs(res);
    }
}

func minimumOneBitOperations(n int) int {
    res, sign := 0, 1
    for n != 0 {
        res += sign * (n ^ (n - 1))
        n &= (n - 1)
        sign *= -1
    }
    if res < 0 {
        return -res
    }
    return res
}

class Solution {
    fun minimumOneBitOperations(n: Int): Int {
        var num = n
        var res = 0
        var sign = 1
        while (num != 0) {
            res += sign * (num xor (num - 1))
            num = num and (num - 1)
            sign *= -1
        }
        return kotlin.math.abs(res)
    }
}

class Solution {
    func minimumOneBitOperations(_ n: Int) -> Int {
        var n = n
        var res = 0
        var sign = 1
        while n != 0 {
            res += sign * (n ^ (n - 1))
            n &= (n - 1)
            sign *= -1
        }
        return abs(res)
    }
}

impl Solution {
    pub fn minimum_one_bit_operations(n: i32) -> i32 {
        let mut n = n;
        let mut res = 0i32;
        let mut sign = 1i32;
        while n != 0 {
            res += sign * (n ^ (n - 1));
            n &= n - 1;
            sign *= -1;
        }
        res.abs()
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

4. Math (Grey Code)

Intuition

This problem has a direct connection to Gray codes. A Gray code is a binary sequence where consecutive numbers differ by exactly one bit. The allowed operations in this problem exactly match how Gray codes transition between values. Converting a Gray code back to its binary index tells us how many steps away it is from zero. The conversion formula involves XORing n with all its right-shifted versions.

Algorithm

Initialize res = n.
While n is not zero:
- Right shift n by 1.
- XOR the result into res.
Return res, which represents the position of the original number in the Gray code sequence.

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        res = n
        while n:
            n >>= 1
            res ^= n
        return res

class Solution {
    /**
     * @param {number} n
     * @return {number}
     */
    minimumOneBitOperations(n) {
        let res = n;
        while (n !== 0) {
            n >>= 1;
            res ^= n;
        }
        return res;
    }
}

class Solution {
    fun minimumOneBitOperations(n: Int): Int {
        var num = n
        var res = n
        while (num != 0) {
            num = num shr 1
            res = res xor num
        }
        return res
    }
}

class Solution {
    func minimumOneBitOperations(_ n: Int) -> Int {
        var n = n
        var res = n
        while n != 0 {
            n >>= 1
            res ^= n
        }
        return res
    }
}

impl Solution {
    pub fn minimum_one_bit_operations(n: i32) -> i32 {
        let mut n = n;
        let mut res = n;
        while n != 0 {
            n >>= 1;
            res ^= n;
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

Common Pitfalls

Misunderstanding the Operations

The two operations allowed (flip the rightmost bit, flip bit i if bit i-1 is 1 and all bits to the right of i-1 are 0) are often misunderstood. Many solutions incorrectly assume you can flip any bit at any time, leading to incorrect operation counts. Carefully trace through small examples like n = 3 to understand the constraints.

Not Recognizing the Gray Code Pattern

This problem has a deep connection to Gray codes, where consecutive numbers differ by exactly one bit. Missing this insight leads to overly complex recursive solutions that are hard to derive and verify. The elegant solution converts the Gray code back to its binary index using iterative XOR.

Integer Overflow in Intermediate Calculations

When computing (k << 1) - 1 or similar expressions, intermediate values can overflow for large inputs near the 32-bit integer limit. In languages like C++ or Java, ensure you handle the bit shifting carefully, especially when k approaches 2^30.

Incorrect Sign Alternation

In iterative solutions that process bits from highest to lowest, the sign must alternate correctly between addition and subtraction. A common bug is initializing the sign incorrectly or flipping it at the wrong point in the loop, leading to off-by-one errors in the final count.

Off-by-One in Bit Position Calculation

Finding the highest set bit requires careful loop conditions. Using while (k < n) instead of while ((k << 1) <= n) or similar variations can cause the algorithm to select the wrong bit position, resulting in incorrect operation counts.