Maximum Number of set bits after flipping a single contagious segment of bits

Problem

Given an integer N, flip exactly one contiguous segment of bits (from index L to R) in its binary representation to maximize the total number of set bits (ones). Return the maximum possible number of ones after performing at most one flip.

Constraints (original):

• N may be large (the original note allowed very large values); practical implementations accept N as a standard integer or as a binary string when N does not fit in native types.

Examples

Example 1

Input: 146
Output: 6
Explanation: 146 in binary is `10010010`. Flipping the contiguous segment indices [1,5] (0-based from left as written) yields `11101110` which has 6 ones.

Solution

We convert the bit-flip problem to a maximum subarray problem (Kadane). Treat each bit b as a value v: v = 1 if b == 0 (flipping this 0 gives +1 one), and v = -1 if b == 1 (flipping a 1 reduces the count by 1). The maximum subarray sum of v gives the best gain in ones achievable by flipping one contiguous segment. Add that gain to the count of existing ones. If all bits are ones (no zeros), the best action is to not flip (gain <= 0), so answer is original number of ones.

Method 1 — Transform + Kadane (optimal)

Intuition

Convert the binary digits to a weight array v where v[i] = 1 when bit i is 0 and v[i] = -1 when bit i is 1. Flipping a segment adds the sum of v over that segment to the total number of ones. The best segment is the maximum-sum contiguous subarray of v (Kadane's algorithm).

Approach

1. Convert N to its binary representation (as a vector/list of bits). If N is provided as a string, parse that string.
2. Count totalOnes = number of ones in the bit array.
3. Build array v where v[i] = 1 if bit[i] == 0 else v[i] = -1.
4. Run Kadane to find bestGain = max(0, max_subarray_sum(v)).
5. Answer = totalOnes + bestGain.

Edge cases:

• If there are no zeros, bestGain will be <= 0, so return totalOnes (do not flip).
• If N == 0, flipping the whole bits yields number of bits set equal to number of bits in representation — treat representation carefully (use at least one bit).

Code

C++

class Solution {
 public:
    int maxOnesAfterFlip(unsigned long long n) {
        if (n == 0) return 1; // binary "0" -> flip gives 1
        vector<int> bits;
        while (n > 0) { bits.push_back(n & 1ULL); n >>= 1; }
        reverse(bits.begin(), bits.end());
        int totalOnes = 0;
        int best = 0, cur = 0;
        for (int b : bits) {
            totalOnes += b;
            int v = (b == 0) ? 1 : -1;
            cur = max(v, cur + v);
            best = max(best, cur);
        }
        return totalOnes + max(0, best);
    }
};

Go

package main

func maxOnesAfterFlipFromInt(n uint64) int {
    if n == 0 {
        return 1
    }
    var bits []int
    for n > 0 {
        bits = append(bits, int(n&1))
        n >>= 1
    }
    // bits are LSB..MSB, iterate reversed
    totalOnes, best, cur := 0, 0, 0
    for i := len(bits) - 1; i >= 0; i-- {
        b := bits[i]
        totalOnes += b
        v := -1
        if b == 0 {
            v = 1
        }
        if cur+v > v {
            cur = cur + v
        } else {
            cur = v
        }
        if cur > best {
            best = cur
        }
    }
    if best < 0 {
        best = 0
    }
    return totalOnes + best
}

func max(a, b int) int { if a > b { return a }; return b }

Java

class Solution {
    public int maxOnesAfterFlip(long n) {
        if (n == 0) return 1;
        List<Integer> bits = new ArrayList<>();
        while (n > 0) {
            bits.add((int)(n & 1));
            n >>= 1;
        }
        int totalOnes = 0;
        int best = 0, cur = 0;
        for (int i = bits.size() - 1; i >= 0; --i) {
            int b = bits.get(i);
            totalOnes += b;
            int v = (b == 0) ? 1 : -1;
            cur = Math.max(v, cur + v);
            best = Math.max(best, cur);
        }
        return totalOnes + Math.max(0, best);
    }
}

Python

from typing import List

class Solution:
    def max_ones_after_flip(self, n: int) -> int:
    # treat n as non-negative integer; if n is huge, provide bits as string externally
    if n == 0:
        return 1
    bits: List[int] = []
    while n > 0:
        bits.append(n & 1)
        n >>= 1
    bits.reverse()
    total_ones = 0
    best = 0
    cur = 0
    for b in bits:
        total_ones += b
        v = 1 if b == 0 else -1
        cur = max(v, cur + v)
        best = max(best, cur)
    return total_ones + max(0, best)

Complexity

• ⏰ Time complexity: O(n) where n is number of bits — each bit is visited once for conversion and once in Kadane.
• 🧺 Space complexity: O(n) to store the bit array (can be reduced to O(1) if bits are streamed and Kadane is run on the fly).