You are given an binary array A of N integers. You are also given an integer K and you need to ensure that no subarray of size greater than or equal to K has average 1.
For this you can perform the below operation:
- Choose any index and flip the bit.
Find the minimum number of operations to acheive the above condition.
Input:
First line contains number of test cases T. For each test case:
- First line contains two space seperated integers N and K.
- Second line contains N space separated integers of the binary array.
Output:
Print T lines , one for each test case. For each test case:
- Print a single line denoting the minimum number of operations that needs to be performed.
Constraints:
- 1≤T≤20000
- 1≤N≤200000
- 1≤K≤N
- 0≤Ai≤1
- Sum of N over all test cases will not exceed 200000.
There are two test cases:
First test case: Since all the elements are initially 1 so only subarray of size 5 has average 1. If we can flip any element from 1 to 0, the array will be [0,1,1,1,1] (After flipping first element) , the average is now .8 for subarray of size 5 which is not equal to 1. So by flipping 1 element we can acheive the goal.
Second test case: Initially array is [1 0 1 1] and K=2, so after the operations are performed no subarray of size 2,3 and 4 should have average equal to 1. If we flip 4th element array becomes, [1 0 1 0] which satisfies the above property. So again answer is 1. Note that initially subarray [1,1] had average 1.
