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.
2 5 5 1 1 1 1 1 4 2 1 0 1 1
1 1
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