Cracking The Coding Interview Together – Problem 5.3: Flip Bit to Win

We have all been there: sitting in an interview, looking at a bit manipulation problem, and feeling a sudden wave of anxiety. Bitwise operations can feel like low-level trivia rather than practical software engineering. But here is the secret: bit manipulation is not about memorizing obscure syntax. It is about understanding how data is represented at the hardware level and using that representation to build incredibly fast, memory-efficient algorithms.

In real-world systems, we are constantly constrained by memory and processing power. When you are processing high-throughput network packets, writing a custom compression algorithm, or working on embedded systems, you cannot afford to allocate massive arrays or convert integers to strings just to analyze their binary representation. You need to process data on the fly, using the hardware's native word size.

Today, we are going to tackle Problem 5.3: Flip Bit to Win from Cracking the Coding Interview. Our shared goal is to design an elegant, production-ready solution that solves this problem in a single pass with O(1) auxiliary space. We will treat the integer not as a static array of characters, but as a dynamic stream of bits.

Problem Statement

The problem asks us to write code to find the length of the longest sequence of 1s you could create by flipping exactly one bit from a 0 to a 1 in an integer.

Let us look at an example to make this concrete:

• Input: 1775 (which is 11011101111 in binary)
• Output: 8

Why 8? If we look at the binary representation 11011101111, we have three sequences of 1s separated by single 0s: a sequence of 2, a sequence of 3, and a sequence of 4. If we flip the 0 at index 4 (counting from the right, 0-indexed), we can merge the sequence of 3 and the sequence of 4 into a single continuous sequence of 8 consecutive 1s (11011111111).

Analyze the Problem Together

Let us break down the constraints and highlight the "Aha!" moment. In Java, a standard integer is a 32-bit signed value represented in two's complement. This means we are dealing with a fixed-size sequence of bits.

The naive approach to this problem is to convert the integer into its binary string representation using Integer.toBinaryString(n), split the string by "0", and then look at adjacent groups of 1s. While this is intuitive, it is highly inefficient. It requires allocating memory for the string, splitting it into multiple substrings, and iterating over those substrings. This results in O(b) space complexity, where b is the number of bits (32 for an integer).

As senior engineers, we want to avoid unnecessary allocations. Can we do this on the fly? Yes! The "Aha!" realization is that we only need to keep track of three things as we scan the bits from right to left:

1. The length of the current sequence of 1s.
2. The length of the previous sequence of 1s (separated from the current sequence by exactly one 0).
3. The maximum length we have seen so far.

Let us compare the naive approach with our optimized bitwise approach:

Questions for the Interviewer

Before jumping into the code, a senior engineer always clarifies the requirements. Here are the questions we should ask our interviewer:

• "Are we dealing with a standard 32-bit signed integer, or should we support 64-bit longs?" (This determines our bit-shifting limits and the maximum possible sequence length).
• "What if the input is already all 1s (e.g., -1 in two's complement)?" (If all bits are 1, we cannot make a longer sequence by flipping a 0, because there are no 0s. The maximum sequence length should be capped at the bit-width of the integer, which is 32).
• "Are we allowed to use built-in language features, or do you want to see pure bitwise operators?" (We should always aim for pure bitwise operators to demonstrate our low-level understanding).

Think About the Solution

Let us design the high-level architecture of our bitwise sliding window. We will iterate through the 32 bits of the integer using an unsigned right shift (>>>). The unsigned shift is critical because it fills the leftmost bits with 0s, preventing infinite loops when dealing with negative numbers.

As we inspect each bit from right to left:

• If the current bit is 1, we increment our currentLength.
• If the current bit is 0, we look ahead to the next bit to see if we can merge across this 0:
  • If the next bit is also 0, we cannot merge. The previousLength must be reset to 0.
  • If the next bit is 1, this 0 can act as a bridge. The previousLength becomes the currentLength, and we reset currentLength to 0.
• At each step, we update our maxLength to be the maximum of itself and previousLength + currentLength + 1. The + 1 represents the 0 bit that we are choosing to flip into a 1.

Let us consider edge cases. If the integer is 0, we can flip any bit to get a sequence of 1, so the answer is 1. If the integer is -1 (all 1s), the answer is 32. Our logic must handle these seamlessly.

Write Code and Explain

Here is the clean, production-ready Java implementation of our optimized bitwise algorithm:

public class FlipBitToWin {

    /**
     * Finds the length of the longest sequence of 1s you could create by flipping
     * exactly one bit from 0 to 1.
     * 
     * @param n the input integer
     * @return the length of the longest sequence of 1s
     */
    public static int longestSequence(int n) { 
        // Edge case: If all bits are 1, we cannot make a longer sequence.
        // In Java, ~-1 is 0. This check handles the all-ones case perfectly.
        if (~n == 0) {
            return Integer.SIZE; // 32
        }

        int currentLength = 0;
        int previousLength = 0;
        int maxLength = 1; // We can always flip at least one 0 to 1 to get a sequence of 1

        while (n != 0) {
            if ((n & 1) == 1) {
                // Current bit is 1: increment the current run
                currentLength++;
            } else {
                // Current bit is 0: check the next bit to see if we can bridge
                // If the next bit is 0, previousLength becomes 0.
                // If the next bit is 1, previousLength becomes currentLength.
                previousLength = ((n & 2) == 0) ? 0 : currentLength;
                currentLength = 0;
            }
            
            // Update the global maximum. The '+ 1' represents the flipped bit.
            maxLength = Math.max(previousLength + currentLength + 1, maxLength);
            
            // Unsigned right shift to process the next bit and handle negative numbers
            n >>>= 1;
        }

        return maxLength;
    }
}

Step-by-Step Walkthrough

Let us trace this code with our example n = 1775 (binary 11011101111):

1. Initial State: currentLength = 0, previousLength = 0, maxLength = 1.
2. Bits 0 to 3 (all 1s): currentLength increments to 4. maxLength becomes max(0 + 4 + 1, 1) = 5.
3. Bit 4 (0): We check the next bit (Bit 5, which is 1). Since (n & 2) != 0, we set previousLength = currentLength = 4, and reset currentLength = 0. maxLength remains 5.
4. Bit 5 to 7 (all 1s): currentLength increments to 3. maxLength becomes max(4 + 3 + 1, 5) = 8.
5. Bit 8 (0): We check the next bit (Bit 9, which is 1). We set previousLength = currentLength = 3, and reset currentLength = 0. maxLength remains 8.
6. Bit 9 and 10 (all 1s): currentLength increments to 2. maxLength remains 8 because 3 + 2 + 1 = 6, which is less than 8.
7. The loop terminates when n becomes 0. The method returns 8.

Time & Space Complexity

Let us analyze the efficiency of our solution:

• Time Complexity: O(b), where b is the number of bits in the integer. For a standard 32-bit integer, the loop runs at most 32 times. This is effectively O(1) constant time, making it incredibly fast and predictable.
• Space Complexity: O(1) auxiliary space. We only allocate three primitive integer variables (currentLength, previousLength, and maxLength) on the stack. No heap allocation occurs, making this solution completely garbage-collection friendly.

Why This Problem Matters (The Senior Perspective)

As senior engineers, we must look beyond the interview sandbox. Why does this pattern matter in production systems?

This problem is a classic example of the Sliding Window pattern applied to bitstreams. In modern software architectures, we often deal with streaming data—whether it is video streaming, real-world IoT sensor data, or high-frequency financial feeds. Being able to process data in a single pass without buffering the entire stream into memory is a vital skill.

Furthermore, this code is inherently thread-safe. Because it does not rely on shared mutable state or external libraries, it can be safely executed across multiple threads in a highly concurrent environment without any synchronization overhead. If you were building a high-performance network parser, this is exactly the kind of low-level optimization that keeps latency low and throughput high.

Final Thoughts

We have successfully taken a potentially tricky bit manipulation problem and solved it using an elegant, O(1) space sliding window algorithm. By focusing on the relationship between adjacent bit sequences, we avoided the memory overhead of string manipulation and built a solution fit for production systems.

As a next step, try adapting this algorithm to find the longest sequence of 1s if you were allowed to flip two bits instead of one. How would you update your state variables to track the extra bridge?

Keep coding, keep optimizing, and we will see you in the next post on The Dev Learnings!