<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>

class Solution:
    def minMoves(self, nums: List[int], k: int) -> int:
        # READ!!!!! https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/solutions/987607/o-n-explanation-with-picture/?envType=list&envId=rfqlj0e6
        # O(N) O(N)
        # 1010101011 => 024679 if k == 5 and if we want to make 02467 for a case, we need 23456
        # 02467 ==> 44444, needs 4+2+2+3 = 11
        # 44444 ==> 23456, -2-1-0-1-2, radius - odd: (k-1)//2 => 2 or even: (k-2)//2 => 2
        # Total cost:
            #1) gethering cost: (4-0)+(4-2)+(6-4)+(7-4) = right:(6+7) - left: (0+2) = right: (cum(i+r) - cum(i))right - left: (cum(i-1)-cum(i-1-r)) 
            #2) repositioning cost = 2+1+0+1+2 = r(r+1)/2 * 2 = r(r+1)
        #nums = [1,0,1,0,1,0,1,1,0,1,1,1]
        #k = 5

        p = [i for i, v in enumerate(nums) if v == 1]
        # p[i]: the position of i-th 1
        n = len(p)
        presum = [0] + list(accumulate(p)) #need one more as always starting from 0
        #presum = [0]*(n+1) # to check the cumulative count of 1 ########################
        # presum[i]: sum(p[0]...p[i-1])
        #for i in range(n):
        #    presum[i+1] = presum[i] + p[i]
        #print(p, presum) # [0, 2, 4, 6, 7, 9, 10, 11] [0, 2, 6, 12, 19, 28, 38, 49] => [0, 0, 2, 6, 12, 19, 28, 38, 49]
        res = inf

        # sliding window
        if k % 2 == 1: # if odd
            radius = (k-1)//2 # when k == 5, radius is 2
            for i in range(radius, n-radius):
                # i-radius ... i ... i+radius
                # move radius to i
                # i+1, ..., i+radius
                right = presum[i+radius+1]-presum[i+1] #19-6 = 13
                # i-radius, ..., i-1
                left = presum[i]-presum[i-radius] # 2-0 = 2
                res = min(res, right-left)
            return res-radius*(radius+1) # repositioning cost is always same
        else:
            radius = (k-2)//2 # even
            for i in range(radius, n-radius-1):
                # i-radius ... i i+1 ... i+radius+1
                # move radius to i (moving to i+1 is also OK)
                # i+1, ..., i+radius+1
                right = presum[i+radius+2]-presum[i+1]
                # i-radius, ..., i-1
                left = presum[i]-presum[i-radius]
                res = min(res, right-left-p[i]) ##### additional p[i] on the right side, not pairing left and right
            return res-radius*(radius+1)-(radius+1)
27700