C++ solution using prefix sum and median
Approach\nUsing the concept of median in every window to minimize distances, ie, moves. Prefix sum is used to calculate distance in every window in O(1) time.\n
# Approach\nUsing the concept of median in every window to minimize distances, ie, moves. Prefix sum is used to calculate distance in every window in O(1) time.\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minMoves(vector<int>& nums, int k) \n    {\n        int n = nums.size();\n        if(k == 1)\n        return 0;\n\n        // get indices of 1s \n        // take window size of k and get the median. Median will minimize number of moves / absolute distance\n        // Here, obviously its not absolute distance from median everytime, because we need to consider elements\n        // to the median\'s right and left as well, but it works here as well\n        vector<int> ones;\n        vector<long> prefix;\n\n        for(int i=0; i<n; i++)\n        {\n            if(nums[i] == 1)\n            {\n                ones.push_back(i);\n\n                if(prefix.size() == 0)\n                prefix.push_back(ones.back());\n\n                else\n                prefix.push_back(prefix.back() + ones.back());\n            }\n        }\n\n        // ones array is already sorted as we are incrementally pushing indices\n        // so, eligible to calculate median directly, without any sorting\n\n        int size = ones.size();\n        int i = 0, j = k - 1;\n        int offset = k / 2;\n\n        long border1 = 0, border2 = 0;\n        long k1 = k;\n        if(k % 2 == 0)\n        {\n            border1 = ((k1/2 - 1) * (k1/2)) / 2;\n            border2 = ((k1/2) * (k1/2 + 1)) / 2;\n        }\n\n        else\n        {\n            border1 = ((k1/2) * (k1/2 + 1)) / 2;\n            border2 = border1;\n        }\n\n        long minMoves = LLONG_MAX;\n        while(j != size)\n        {\n            long median = ones[i + offset];\n            long leftNum = k/2 + 1;\n            long rightNum = (k % 2 == 0) ? (k/2 - 1) : k/2;\n\n            int leftSubtract = (i == 0) ? 0 : prefix[i - 1];\n            long leftSum = leftNum * median - (prefix[i + offset] - leftSubtract);\n            long rightSum = prefix[j] - prefix[i + offset] - rightNum * median;\n\n            // for(int k=i; k<=j; k++)\n            // sum += abs(ones[k] - median);\n\n            // cout << "j: " << j << " " << sum - border1 - border2 << endl;\n            minMoves = min(minMoves, leftSum + rightSum);\n            ++i;\n            ++j;\n        }\n\n        return (int)(minMoves - border1 - border2);\n    }\n};\n```
['Array', 'Math', 'Sliding Window', 'Prefix Sum', 'C++']