# 995. Minimum Number of K Consecutive Bit Flips

### Greedy

when meet 0, we flip

T: O(nk)

```java
class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length;
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                for (int j = i; j < i+k; j++) {
                    if (j >= n) {
                        return -1;
                    }
                    nums[j] = (nums[j]+1)%2;
                }
                result++;
            }
        }
        return result;
    }
}

/**
T: O(nk)
greedy

when meet 0, we flip k elements
in the end, if flip k is out of boundary, it must -1
(why this greedy ok? if in order to flip some 0, and we flip some 1 before 0, 
it would't be better because we might to handle more flips in the begining, it's a chain reaction!)

0 0 0 1 0 1 1 0
-----     
        1 0 0
          

0 0 0 1 1 2 3 3
but T: O(nk) will be TLE

-> better solution, sweep line

k = 3
0 0 0 1 0 1 1 0
+      
      -
 */
```

## use diff array

T: O(n)

S: O(n)

```java
class Solution {
/** 
    [0,0,0,1,0,1,1,0], k = 3
diff[0,0,0,0,0,0,0,0]
currentFlip = 0
result = 0

currentFlip = 1
result = 1
diff[0,0,0,-1,0,0,0,0,0]

1+0 = 1 (in next round it's all 1, so our flip works!)
1+0 = 1
diff [0, 0, 0, -1, 0, 0, 0 ,0, 0]
      x. x. x   n
currentFlip += diff[i] = 1-1 = 0 -> so no flip now
then A[i] + currentFlip) % 2 = (1 + 0) % 2 = 1
-> no flip
      currentFlip = 0 
      result = 1        
diff [0, 0, 0, -1, 0, 0, 0 , -1, 0]
     [0, 0, 0, 1,  0, 1, 1,  0]
                   f
  A[i] + currentFlip) % 2 = 0 + 0 ) % 2= 0
  do flip
    currentFlip = 1
    result = 2
      0. 1  2. 3.  4. 5
diff [0, 0, 0, -1, 0, 0, 0 ,-1, -1]
     [0, 0, 0, 1,  0, 1, 1,  0]
                      f
 currentFlip + diff[i] = 1
 1 + num[i](1) = 2    %2 = 0
 do flip
    currentFlip = 2
    result 3  
diff [0, 0, 0, -1, 0, 0, 0 ,-1, -1]
     [0, 0, 0, 1,  0, 1, 1,  0]
                         n
  currentFlip + diff[i] = 2 + 0 = 2
  2+ 1 = 3 %2 = 1

diff [0, 0, 0, -1, 0, 0, 0 ,-1, -1]
     [0, 0, 0, 1,  0, 1, 1,  0]
                             n
2 - 1 = 1
1 + 0 = 1 % 2 = 1 -> no flip
-> end!
so result = 3                                                        
**/
    public int minKBitFlips(int[] A, int K) {
        int n = A.length;
        int[] diff = new int[n + 1];  // Difference array to track flips
        int flipCount = 0;            // Number of flips performed
        int currentFlip = 0;          // Current number of flips at position i
        
        for (int i = 0; i < n; i++) {
            currentFlip += diff[i];
            // System.out.println("currentFlip:" + currentFlip);
            // System.out.println("diff:" + Arrays.toString(diff));
            // If A[i] is 0 and we have even number of flips or A[i] is 1 and we have odd number of flips
            if ((A[i] + currentFlip) % 2 == 0) {
                //System.out.println(i);
                if (i + K > n) { // 5+3 = 8 == n
                    return -1;  // Impossible to flip the subarray of length K
                }
                flipCount++;
                currentFlip++; // why only need add in this variable? because this has continuous 效力 just like diff[i] to diff[i+k-1] all add 1 
                // so we only need to minus in diff[i+k]--, then next we do the currentFlip += diff[i]; it will eliminate the 1 
                diff[i + K]--;  // To revert the effect of the flip after K steps
            }
        }
        
        return flipCount;
    }
}

/**
T: O(n)
currentFlip = 0
diff [0, 0, 0]
==0 -> do flip
flipCount = 1
currentFlip = 1
diff[i+k] = diff[1]--;
diff [0, -1, 0]
[0,1,0]
currentFlip + -1 = 1 -1 = 0
1+0 = 1 pass



[0,0,0,1,0,1,1,0], k = 3

currentFlip = 0
flipCount
diff [0, 0, 0, 0, 0, 0, 0 ,0]


---------
T: O(nk)
greedy

when meet 0, we flip k elements
in the end, if flip k is out of boundary, it must -1
(why this greedy ok? if in order to flip some 0, and we flip some 1 before 0, 
it would't be better because we might to handle more flips in the begining, it's a chain reaction!)

0 0 0 1 0 1 1 0
-----     
        1 0 0
          

0 0 0 1 1 2 3 3
but T: O(nk) will be TLE

-> better solution, sweep line

k = 3
0 0 0 1 0 1 1 0
+      
      -
 */
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/prefix-sum/diff-array-cha-fen/995.-minimum-number-of-k-consecutive-bit-flips.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.