nikunjsoni

1703

Apr 4th, 2021
89
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # define ll long long
  2. class Solution {
  3. public:
  4.     int minMoves(vector<int>& nums, int k) {
  5.         ll i, n = nums.size(), l, r;
  6.         vector<ll> a;   // Indexes array
  7.         a.push_back(0); // To make indexes array the same size as prefix array
  8.         for(i=0; i<n; i++)
  9.             if(nums[i])
  10.                 a.push_back(i);
  11.         n = a.size();
  12.        
  13.         vector<ll> prefix(n, 0);  // Prefix array
  14.         for(i=1; i<n; i++)     // prefix[i] = sum of all elements from a[0] to a[i]
  15.             prefix[i] = prefix[i - 1] + a[i];
  16.        
  17.         ll ans = LONG_LONG_MAX;
  18.        
  19.         // Rolling window [l...r] of length k
  20.         for(l=1,r=k; r<n; ++l, ++r) {
  21.             ll mid = (l + r) / 2;  // Mid-point - current element
  22.             ll radius = mid - l;   // How many elements on each side
  23.             ll right = prefix[r] - prefix[mid];     // Prefix of radius elements to the right of mid
  24.             ll left = prefix[mid - 1] - prefix[l - 1];  // Prefix of radius elements to the left of mid
  25.             ll subtract = (radius) * (radius + 1);  // Once all elements are equal, make it a sequence
  26.             if(k % 2 == 0) {        // Special case if k is even
  27.                 subtract += (a[mid] + (radius + 1));     // Deduct current element and also deduct the cost of the furthest right element
  28.             }
  29.             ans = min(ans, right - left - subtract);
  30.         }
  31.         return ans;
  32.     }
  33. };
RAW Paste Data