O(n) explanation with picture
Experiment for explaining with picture, with a few words.\n\nUse sliding window to calculate the cost of every consecutive k 1s.\n\nHope that helps!\n\n\n\nProv
Experiment for explaining with picture, with a few words.\n\nUse **sliding window** to calculate the **cost** of every **consecutive k 1s**.\n\nHope that helps!\n\n![1703.png](https://i.loli.net/2020/12/27/aPSNTZybtBFzHqW.png)\n\nProvide the code for clarification.\n\nYou can combine odd and even cases together with some tricks, we separate them here for readability.\n\n**(Follow up: Can you combine odd and even cases together?)**\n**(Follow up2: If the input puts some 1s in the same positions, does this method still apply? What modification we need?)**\n**(Follow up3: another similar one https://atcoder.jp/contests/abc229/tasks/abc229_g)**\n\n```python\nclass Solution:\n    def minMoves(self, nums: List[int], k: int) -> int:\n        p = [i for i, v in enumerate(nums) if v == 1]\n        # p[i]: the position of i-th 1\n        n = len(p)\n        presum = [0]*(n+1)\n        # presum[i]: sum(p[0]...p[i-1])\n        for i in range(n):\n            presum[i+1] = presum[i]+p[i]\n\n        res = inf\n\n        # sliding window\n        if k % 2 == 1:\n            # if odd\n            radius = (k-1)//2\n            for i in range(radius, n-radius):\n                # i-radius ... i ... i+radius\n                # move radius to i\n                # i+1, ..., i+radius\n                right = presum[i+radius+1]-presum[i+1]\n                # i-radius, ..., i-1\n                left = presum[i]-presum[i-radius]\n                res = min(res, right-left)\n            return res-radius*(radius+1)\n        else:\n            # even\n            radius = (k-2)//2\n            for i in range(radius, n-radius-1):\n                # i-radius ... i i+1 ... i+radius+1\n                # move radius to i (moving to i+1 is also OK)\n                # i+1, ..., i+radius+1\n                right = presum[i+radius+2]-presum[i+1]\n                # i-radius, ..., i-1\n                left = presum[i]-presum[i-radius]\n                res = min(res, right-left-p[i])\n            return res-radius*(radius+1)-(radius+1)\n```\n\n
['Sliding Window', 'Python']