Minimum K Consecutive Bit Flips

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Minimum number of k-bit flips to make all bits 1. Greedy sliding window.

Algorithm

1Sliding window: track flips in current window with a difference array. Flip at position i if current bit is 0 (accounting for flips).

Common Pitfalls

•Same as LC 995. Use flip difference array to track effect in O(1). O(n) overall.

Minimum K Consecutive Bit Flips.java

Java

// Approach: Sliding window with a flip count array. Track pending flips without actually modifying the array.
// Time: O(n) Space: O(n)
class Solution {
    public int kBitFlips(int[] arr, int k) {
        int n = arr.length;
        int flips = 0;
        int flip = 0;
        int[] isFlipped = new int[n];

        for (int i = 0; i < n; i++) {
            if (i >= k)
                flip ^= isFlipped[i - k];

            if ((arr[i] ^ flip) == 0) {
                if (i + k > n)
                    return -1;
                isFlipped[i] = 1;
                flip ^= 1;
                flips++;
            }
        }
        
        return flips;
    }
}

Was this solution helpful?