Go | Prefix Array
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n1. Find consecutive 1\'
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Find consecutive 1\'s at max size 3, should be <= k  \n    Why? 1,1,1 <- can be directly used to pick at most 3 1\'s using operation 2 directly. Only 1 move for each adj and 0 for middle. So total moves = 2 (maxConseq-1 i.e. 3-1)\n2. For the remaining 1\'s to pick up, check if maxChanges is enough\n   Why? as we picked consequtives one\'s which could be picked up less moves, next is to pick up remaining ones. Action 1 takes 2 moves to pick up 1 as first change 0 to 1 and then move it to index that we want, so that we can pick up that 1. Swap action + pick = 2. \n    a. If enough then return- 2 * (remaining 1\'s i.e. k-maxConseq) + (maxConseq - 1)\n    b. Edge case like 0 maxConseq, handled in code - max(maxConseq-1, 0)\n3.  If not enough, try find (k-maxChanges) 1\'s which are close to each other. Optimally find it using prefix array.\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfunc minimumMoves(nums []int, k int, maxChanges int) int64 {\n    // find max consequetive 1\'s\n    maxConseq := min(k, findMaxConseq(nums))\n\n    rem := k-maxConseq\n    if maxChanges >= rem {\n        return max(int64(maxConseq)-1, 0) + int64(rem) * 2\n    }\n\n    rule1Moves := 2 * int64(maxChanges)\n    k -= maxChanges\n    ones := findOnes(nums)\n    pref := calcPref(ones)\n    n := len(ones)\n    var res int64 = math.MaxInt64\n    for l := 0; l <= n-k; l++ {\n        r := l+k-1\n        m := l+(r-l)/2\n        pos := int64(ones[m])\n\n        lsize, rsize := int64(m-l+1), int64(r-m+1) \n        lsum, rsum := pref[m+1]-pref[l], pref[r+1]-pref[m]\n        \n        ldiffs, rdiffs := pos*lsize-lsum, rsum-pos*rsize\n        \n        res = min(res, ldiffs + rdiffs + rule1Moves)\n    }\n\n    return res\n}\n\nfunc findMaxConseq(nums []int) int {\n    cnt := 0\n    maxCnt := 0\n    for _, n := range nums {\n        if n == 1 {\n            cnt++\n        } else {\n            cnt = 0\n        }\n        if cnt == 3 {\n            return cnt\n        }\n        maxCnt = max(maxCnt, cnt)\n    }\n    return maxCnt\n}\n\nfunc findOnes(nums []int) []int {\n    var res []int\n    for i, n := range nums {\n        if n == 1 {\n            res = append(res, i)\n        }\n    }\n    return res\n}\n\nfunc calcPref(nums []int) []int64 {\n    res := make([]int64, len(nums)+1)\n    for i, v := range nums {\n        res[i+1] = res[i] + int64(v)\n    }\n    return res\n}\n```
['Go']