java prefix Sum
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public long minimumMoves(int[] nums, int k, int maxChanges) {\n\n        int maxLen = 0;\n        int len = 0;\n        for(int i = 0; i < nums.length; i++) {\n            if ( nums[i] == 1 ) len++;\n            else len = 0;\n            maxLen = Math.max(maxLen, len);\n        }\n        \n        List<Long> list = new ArrayList<Long>();\n        for(int i = 0; i < nums.length; i++) {\n            if ( nums[i] == 1 ) list.add((long)i);\n        }\n        \n        if ( list.size() == 0 ) return k*2;\n        if ( k == 1 ) return 0;\n\n        long preSum[] = new long[list.size()];\n        \n        preSum[0] = list.get(0);\n        for(int i = 1; i < list.size(); i++) {\n            preSum[i] = preSum[i-1] + list.get(i);\n        }\n\n        long add = 0;\n        if ( list.size() < k ) {\n            long diff = k -list.size();\n            k -= diff;\n            add += diff * 2;\n            maxChanges -= diff;\n        }\n\n        long min = Long.MAX_VALUE;\n        int start = 0;        \n\n        if ( Math.min(maxLen,3) + maxChanges >= k) {\n            if ( maxLen == 1 ) return (long)(k -1) * 2 + add;\n            else if ( maxLen == 2 ) return (long) Math.max(0,(k-2)) * 2 + add +Math.min(k-1, 1);\n            else return (long) Math.max(0,(k-3)) * 2 + add + Math.min(k-1, 2);\n        }\n        \n        if ( k > maxChanges ) {\n            k -= maxChanges;\n            add += maxChanges * 2;\n\n        }    \n\n        for(int i = k-1; i < list.size(); i++) {\n\n            if ( k % 2 == 0 ) {\n\n                int median1 = start + k/2-1;\n                int median2 = start + k/2;\n\n                long leftSum = (median1-1 < 0? 0 :preSum[median1-1]- ((start-1<0)?0:preSum[start-1]));\n                long rightSum = preSum[i] - preSum[median1];\n                long leftCnt = median1 -start;\n                long rightCnt = i - median1;\n\n                long opCnt = Math.abs(leftCnt * list.get(median1) - leftSum) + Math.abs(rightCnt * list.get(median1) - rightSum);\n\n\n                leftSum = (median2-1 < 0? 0 :preSum[median2-1]- ((start-1<0)?0:preSum[start-1]));\n                rightSum = preSum[i] - preSum[median2];\n                leftCnt = median2 -start;\n                rightCnt = i - median2;\n\n                opCnt = Math.min(opCnt, Math.abs(leftCnt * list.get(median2) - leftSum) + Math.abs(rightCnt * list.get(median2) - rightSum)) ;\n\n                min = Math.min(min, opCnt + add);\n\n            } else{\n                int median = start + k/2;\n                int cnt = k/2;\n\n                long leftSum = (median-1<0?0:preSum[median-1] - ((start-1<0)?0:preSum[start-1]));\n                long rightSum = preSum[i] - preSum[median];\n\n                long opCnt = Math.abs(cnt * list.get(median) - leftSum) + Math.abs(cnt * list.get(median) - rightSum);\n                \n                min = Math.min(min, opCnt + add);\n\n            }\n            start++;\n        }\n        \n        return min;\n    }\n}\n```
['Prefix Sum', 'Java']