Minimum Number of K Consecutive Bit Flips

Minimum Number of K Consecutive Bit Flips - Problem

Array Bit Manipulation Queue Sliding Window Prefix Sum Hard

You are given a binary array nums and an integer k. A k-bit flip is choosing a subarray of length k from nums and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of k-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

A subarray is a contiguous part of an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [0,1,0], k = 1

› Output: 2

💡 Note: Flip nums[0] to get [1,1,0], then flip nums[2] to get [1,1,1]. Total 2 flips needed.

Example 2 — Larger K

$ Input: nums = [1,1,0], k = 2

› Output: -1

💡 Note: No matter how we flip, we cannot make all elements 1. The last element cannot be covered by any valid 2-flip.

Example 3 — Multiple Flips

$ Input: nums = [0,0,0,1,0,1,1,0], k = 3

› Output: 3

💡 Note: Flip [0,0,0] to [1,1,1], flip [0,1,1] to [1,0,0], flip [0,0,x] at the end. Total 3 flips.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Binary array [0,1,0] with k=1

Process

Apply minimum flips to make all bits 1

Output

Return minimum number of flips: 2

Key Takeaway

🎯 Key Insight: Track flip effects efficiently using differential arrays instead of simulating each flip operation

Asked in

G Google 25 f Facebook 18 a Amazon 12

The key insight is to use a differential array to efficiently track when flip effects start and end, avoiding the need to actually flip bits or maintain a queue. The optimal approach processes each position in O(1) time. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Differential Array Optimization	O(n)	O(n)	Use differential array to track flip effects in O(1) time per position
Sliding Window with Flip Counter	O(n)	O(n)	Track active flips using a sliding window to avoid actual bit manipulation
Brute Force Simulation	O(n*k)	O(1)	Simulate each flip operation by actually modifying the array

Differential Array Optimization — Algorithm Steps

Use differential array to mark flip boundaries
Compute running sum to get active flip count
Check if current effective bit is 0
Add flip if needed and mark in differential array

Visualization

Tap to expand

Step-by-Step Walkthrough

Mark Boundaries

Use differential array to mark flip start/end

Running Sum

Compute active flips from differential array

Efficient Update

O(1) updates without queue operations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    int flips = 0;
    int flipCount = 0;
    int* diff = (int*)calloc(numsSize, sizeof(int));
    
    for (int i = 0; i < numsSize; i++) {
        flipCount += diff[i];
        
        // Current bit value after considering flips
        int currentBit = flipCount % 2 == 0 ? nums[i] : 1 - nums[i];
        
        if (currentBit == 0) {
            if (i + k > numsSize) {
                free(diff);
                return -1;
            }
            
            // Start a flip at position i
            flips++;
            flipCount++;
            
            // Mark end of flip in differential array
            if (i + k < numsSize) {
                diff[i + k]--;
            }
        }
    }
    
    free(diff);
    return flips;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array with O(1) operations per element

✓ Linear Growth

Space Complexity

O(n)

Differential array of size n to track flip boundaries

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Differential Array Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler