C++ Detailed Explanation
Find all indices of nums[i]=1, storing them in another array (I will name it array A)\n\nThen using sliding window technique to compute the cost of every k cont
Find all indices of nums[i]=1, storing them in another array (I will name it array A)\n\nThen using sliding window technique to compute the cost of every k continuous index of 1s\n\nThe problem can be converted into transforming an array of size k: a=[a[0], a[1],..., a[k-1]] to [x,x+1,...,x+(k-1)] with minimum cost.\n\nHere comes the tricky part: how can we find the value of x? I suggest you have a fundamental grasp of derivation before reading the following.\n\nConversion\'s cost: y=|x-a[0]|+|x+1-a[1]|+...+|x+k-1+a[k-1]|\n\t\t\t\t = |x-a[0]|+|x-(a[1]-1)|+...+|x-(a[k-1]-(k-1))|\n\t\t\t\t \n  \nDerivation : y\' =(x-a[0])/|x-a[0]|+ (x-(a[1]-1))/|x-(a[1]-1)| +...+ (x-(a[k-1]-(k-1)))/|x-(a[k-1]-(k-1))|\n\nArray a : a[0] < a[1] < a[2] < ... < a[k-1]\n=> a[0] <= a[1]-1 <= a[2]-2 <= ...  <= a[k-1]-(k-1)\n\n![image](https://assets.leetcode.com/users/images/39a7fe99-33d3-428a-93bd-0feea5ee74a6_1682450214.0241683.jpeg)\n\nThis raises another question, how can we find f ?\nwe can see that y\' is the sum of the set of elements in the form of (x-v)/|x-v|\n\n(x-v)/|x-v|=1 (if x>v)\n(x-v)/|x-v|=-1 (if x<v)\nTo make y>=0, the number of 1s have to be greater or equal to -1s one\n\nThe solution now is quite straightforward. f is a median of the subsequences array [a[0],a[1]-1,a[2]-2,...,a[k-1]-(k-1)];\n\nTo summarize: in order to make y minimum, x has to be equal to f.\n\nNow then, how can we calculate the cost with O(n) complexity with knowing x?\n\nWe will use the prefix and the following formula :\n\nu[1]+u[2]+u[3]+u[4] +...+u[n] = n*(u[1]+u[n])/2; \n( whereas every subtraction of every continuous 2 elements is equal) \n\nMy code ( not really well-optimized) :\n```\nclass Solution {\npublic:\n    long long temp;\n    long long ans=LLONG_MAX,mid,len1,len2,val1,val2,x;\n    vector<long long> A;\n    int minMoves(vector<int>& nums, int k) {\n        for(int i=0;i<=nums.size()-1;i++)\n            if(nums[i]==1) A.push_back(i);\n        vector<long long> prefix(A.size());\n        prefix[0]=A[0];\n        for(int i=1;i<=A.size()-1;i++)\n        {\n            prefix[i]=prefix[i-1]+A[i];\n        }\n        for(int i=k-1;i<=A.size()-1;i++)\n        {\n            mid=(i+i-k+1)/2;\n            len1=mid-(i-k+1)+1;\n            len2=k-len1;\n            x=A[mid]-len1+1;\n            temp=(i-k+1==0)? prefix[mid] : prefix[mid]-prefix[i-k];\n            val1=x-(temp-len1*(x+x+len1-1)/2);\n            val2=(prefix[i]-prefix[mid]-len2*(x+len1+x+len2+len1-1)/2)-x;\n            if(ans>val1+val2) ans=val1+val2;\n        }\n        return ans;\n    }\n};\n```
['C', 'Sliding Window', 'Prefix Sum']