1611. Minimum One Bit Operations to Make Integers Zero

UnknownView on LeetCode

Dynamic Programming Bit Manipulation

Time: O(log n)

Space: O(log n)

Intuition

Minimum number of bit flips to convert 0 to n. 0 can reach any number; think in terms of paths through XOR operations.

Algorithm

1BFS from 0. At each state x: can XOR with any power of 2 (flip a bit). Find minimum steps to reach n.
2Or: count number of 1-bits in n + (trailing zeros before highest bit) type analysis.

Common Pitfalls

•BFS on bit states. States are all numbers reachable. Distance = min flips.

1611.cs

// Approach: Gray code recursion — f(n) = f(n XOR (highBit | highBit>>1)) + 1 + highBit - 1.
// Time: O(log n) Space: O(log n)

public class Solution
{
    public int MinimumOneBitOperations(int n)
    {
        if (n == 0)
            return 0;
        int x = 1;
        while (x * 2 <= n)
            x <<= 1;
        return MinimumOneBitOperations(n ^ (x | (x >> 1))) + 1 + x - 1;
    }
}

Was this solution helpful?