# [1674. Minimum Moves to Make Array Complementary](https://leetcode.com/problems/minimum-moves-to-make-array-complementary/)
##### tags: `leetcode`

[TOC]

## Description
You are given an integer array `nums` of **even** length n and an integer `limit`. In one move, you can replace any integer from `nums` with another integer between `1` and `limit`, inclusive.

The array `nums` is **complementary** if for all indices `i` (**0-indexed**), `nums[i] + nums[n - 1 - i]` equals the same number. For example, the array ``[1,2,3,4]`` is complementary because for all indices `i`, `nums[i] + nums[n - 1 - i] = 5`.

Return the **minimum** number of moves required to make `nums` **complementary**.
### Example

Input: nums = [1,2,4,3], limit = 4
Output: 1
Explanation: In 1 move, you can change nums to [1,2,2,3] (underlined elements are changed).
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary.

### Constraints

* n == nums.length
* 2 <= n <= 105
* 1 <= nums[i] <= limit <= 105
* n is even.

## Ideas
* 根據題目，由於修改後的數字相加都要相同，我們可以假設修改後的數字介於[2, limit * 2]
* 觀察修改數字的規則，一對數字修改只有**三**種可能 :
* 2 moves: 兩個數字都修改
* 1 moves: 其中一個數字修改
* 0 moves: 數字不變
* 因為修改的範圍有限制所以又要細分!!! (在這裡想很久Orz)
* 假設 m, M = 兩數中較小值, 較大值
* 2 moves: 修改後的值落在 [2, m + 1)
* 1 move: in [m + 1, M + limit + 1) except m + M
* 0 move: at m + M
* 1 move: in [m + M + 1, M + limit + 1)
* 2 moves: in [M + limit + 1, 2 * limit]
* **prefix sum** + **line sweep**
* 在每個區間的開頭/結尾去維持moves的次數
* 最終在presum求min.

## Code
python3

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        moves = [0] * (limit * 2 + 2)
        n = len(nums)
        st, ed = 0, n - 1
        for i in range(n // 2):
            m, M  = nums[i], nums[-i-1]
            if M < m:
                m, M = M, m
                
            # moves[0] += 2               # 2 moves in [2, m + 1)
            moves[m + 1] -= 1           # 1 moves in [m + 1, M + limit + 1) except m + M
            moves[m + M] -= 1           # 0 move at m + M
            moves[m + M + 1] += 1       # 1 moves in [m + M + 1, M + limit + 1)
            moves[M + limit + 1] += 1   # 2 moves in [M + limit + 1, 2 * limit]
        
        
        for i in range(1, len(moves)):
            moves[i] += moves[i - 1]
            
        # return min(moves)     # line 10th 等同 + n
        return  min(moves) + n

c++

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        int n = nums.size();
        vector<int> line(limit * 2 + 2, 0);
        for (int i = 0; i < n / 2; ++i) {
            int m = nums[i], M = nums[n - i - 1];
            if (M < m)
                swap(M, m);
            
            --line[m+1];
            --line[m + M];
            ++line[m + M + 1];
            ++line[M + limit + 1];
        }
        int res = INT_MAX;
        for (int i = 1; i < line.size(); ++i){
            line[i] += line[i - 1];
            res = min(res, line[i]);
        }
        return res + n;
    }
};