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 \leq T \leq 20000\)
- \(1 \leq N \leq 200000\)
- \(1 \leq K \leq N\)
- \( 0 \leq A_i \leq 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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor