3854. Minimum Operations to Make Array Parity Alternating

You are given an integer array nums.

An array is called parity alternating if for every index i where 0 <= i < n - 1, nums[i] and nums[i + 1] have different parity (one is even and the other is odd).

In one operation, you may choose any index i and either increase nums[i] by 1 or decrease nums[i] by 1.

Return an integer array answer of length 2 where:

• answer[0] is the minimum number of operations required to make the array parity alternating.
• answer[1] is the minimum possible value of max(nums) - min(nums) taken over all arrays that are parity alternating and can be obtained by performing exactly answer[0] operations.

An array of length 1 is considered parity alternating.

class Solution {
    vector<int> helper(vector<int> A, int op) {
        vector<int> changed, nchanged;
        for(auto& n : A) {
            if((n & 1) == op) nchanged.push_back(n);
            else changed.push_back(n);
            op = !op;
        }
        int cnt = changed.size();
        sort(begin(changed), end(changed));
        sort(begin(nchanged), end(nchanged));
        int mi = INT_MIN, ma = INT_MAX;
        if(changed.empty()) {
            return {cnt, nchanged.back() - nchanged.front()};
        }
        if(nchanged.empty()) {
            return {cnt, abs(changed.back() - 1 - (changed.front() + 1))};
        }
        if(changed.size() == 1) {
          if(nchanged.size() == 1) {
              return {cnt, min(abs(nchanged[0] - (changed[0] - 1)), abs(nchanged[0] - (changed[0] + 1)))};
          }
          int l = nchanged.front(), r = nchanged.back();
          vector<int> C{changed[0] + 1, changed[0] - 1};
          int diff = INT_MAX;
          for(auto& c : C) {
              diff = min(diff, max(r,c) - min(l,c));
          }
          return {cnt, diff};
        }
        vector<int> base{nchanged[0]};
        if(nchanged.size() != 1) base.push_back(nchanged.back());
        int diff = INT_MAX;
        vector<int> ops{-1,1};
        for(auto& op1 : ops) {
            for(auto& op2 : ops) {
                vector<int> now = base;
                now.push_back(changed[0] + op1);
                if(changed.size() != 1) now.push_back(changed.back() + op2);
                sort(begin(now), end(now));
                diff = min(diff, now.back() - now.front());
            }
        }
        return {cnt,diff};
    }
public:
    vector<int> makeParityAlternating(vector<int>& nums) {
        return min(helper(nums,0), helper(nums,1));
    }
};