<p>You are given an integer array, <code>nums</code>, and an integer <code>k</code>. <code>nums</code> comprises of only <code>0</code>&#39;s and <code>1</code>&#39;s. In one move, you can choose two <strong>adjacent</strong> indices and swap their values.</p>

<p>Return <em>the <strong>minimum</strong> number of moves required so that </em><code>nums</code><em> has </em><code>k</code><em> <strong>consecutive</strong> </em><code>1</code><em>&#39;s</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,0,0,1,0,1], k = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong> In 1 move, nums could be [1,0,0,0,<u>1</u>,<u>1</u>] and have 2 consecutive 1&#39;s.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,0,0,0,0,0,1,1], k = 3
<strong>Output:</strong> 5
<strong>Explanation:</strong> In 5 moves, the leftmost 1 can be shifted right until nums = [0,0,0,0,0,<u>1</u>,<u>1</u>,<u>1</u>].
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,0,1], k = 2
<strong>Output:</strong> 0
<strong>Explanation:</strong> nums already has 2 consecutive 1&#39;s.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>nums[i]</code> is <code>0</code> or <code>1</code>.</li>
	<li><code>1 &lt;= k &lt;= sum(nums)</code></li>
</ul>

/*[1,0,0,1,0,1] here it is a linear array
Here its forbidden to swap any two random indices swapping is only allowed for adjacent indices.
obj:-
1) no. of swaps (distance travelled) required to move from index i to j is j-i
2) Array that stores indexes of 1 describes no of swaps required to move form current index to 0th index
2) By prefixing indices of 1 we can calculate total distance to move all ones till that index to 0th position for example
1 0 0 1 1 1 0 0 0 1 1  1  0  0  0  1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
pf[11]= 42
Means 42 swaps required to move all ones to 0th index from 11th index
4) In 1-D minimum distance of one to all ones is its centre, if k is even then last element of 1st half is considered as centre k/2, if k is odd then k/2
Approach:-
Sliding window 
Approach here is slightly tricky
1) create a window having k ones
2) Calculate cost or total distance to move all ones to centre->d1
3) Calculate distance or cost to distribute all ones to either side of centre->d2
4) In every window take minimum of d1-d2
Why we are moving to centre?
If we can consider any of the given 1 as a reference then we can reduce movement of one 1. if we can consider most nearest one to all ones then it will be further more optimal
How to calculate cost to move at centre?
1 0 0 1 0 1 1 
3 4 5 6 7 8 9 
if k is even k=4
here centre is 6
Cost to move all 1's to centre= 6-3(left part)+((9-6)+(8-6))(right part)
                              = 6-3+9-6+8-6
                              =9+8(cost of moving all ones on right to 0th index)-6(cost of moving mid)-3(cost of moving all ones on left to 0th index)
                              =pf[r]-pf[mid]+a[mid]+pf[mid-1]-pf[l-1](to removing cost of moving all elements outside window)
                              =pf[r]-2*pf[mid]-pf[l-1]
Cost to redistrubute all ones around centre=1(left side)+1(right side)+1(rightmost side)
if k is odd k-3
1 0 0 1 0 1 
3 4 5 6 7 8
cost of moving all 1's to centre =6-3(left part)+8-6(right part)
                                 =6-3+8-6
                                 =8-3
                                 =pf[r]-pf[mid]-pf[mid-1]+pf[l-1]
                                 */
                                 typedef long long ll;
class Solution {
public:
    int minMoves(vector<int>& nums, int k) {
        vector<ll>pf{0};
        for(int i=0;i<nums.size();++i)
            if(nums[i]) pf.push_back(i);
        int n=pf.size();
        for(int i=1;i<n;++i) pf[i]+=pf[i-1];
        int ret=INT_MAX;
        for(int l=1,r=k;r<n;++l,++r){
            int mid=(l+r)/2;
            ll right=pf[r]-pf[mid];
            ll left=pf[mid-1]-pf[l-1];
            int rad=mid-l;
            ll subs=(ll)rad*rad+rad;
            if(k%2==0){
                left+=pf[mid]-pf[mid-1];
                subs+=rad+1;
            }
            ret=min((ll)ret,right-left-subs);
        }
        return ret;
    }
};
140300