Prefix sum O(n + limit) with detailed examples and pseudocode
Intuition\n\nFor each pair of numbers (at index i and N - 1 - i) l and r:\n- By 2 moves we can get any number between [2, limit\2] (including move a number to t
## Intuition\n\nFor each pair of numbers (at index i and N - 1 - i) `l` and `r`:\n- By 2 moves we can get any number between [2, limit\\*2] (including move a number to the same number)\n- After only one move (change one of the numbers to a number between 1 and limit)\n  - The minimum sum we can get is `(min(l, r) + 1)` (let this be `oneMoveMin`)\n  - The maximum sum we can get is `(max(l, r) + limit)` (let this be `oneMoveMax`)\n- We need no move to get `(l + r)` (let this be `justGood`)\n\nTherefore, to get:\n- `[~, oneMoveMin - 1]` - 2 moves\n- `[oneMoveMin, justGood-1]` - 1 move\n- `[justGood]` - 0 move\n- `[justGood + 1, oneMoveMax]` - 1 move\n- `[oneMoveMax + 1, ~]` - 2 moves\n\nFor each pair of numbers\n- We start with 2 moves\n- From `oneMoveMin` we need 1 less move\n- From `justGood` we need another 1 less move\n- From `justGood + 1` we need 1 more move\n- From `oneMoveMax + 1` we need another 1 more move\n\nFor all numbers\n- We can at most move N times\n- From 2 to limit\\*2, we accumulate the number of moves all pairs of numbers subtract/add\n- Find the smallest\n\n## Examples\n\nSuppose we have a pair of numbers `(3, 5)` and limit `6`\n- oneMoveMin (`lo`) = replace bigger number with 1 = 3 + (5->1) = 3 + (1) = 4\n- oneMoveMax (`hi`) = replace smaller number with limit = (3->6) + 5 = (6) + 5 = 11\n- justGood (`mi`) = 3 + 5 = 8\n\nThe diagram below shows minimum (optimal) number of moves (`\u25CB`) we need to get each target\n```text\nNo way    | \u25CB  \u25CB                          \u25CB |\nget       | \u25CB  \u25CB  \u25CB  \u25CB  \u25CB  \u25CB     \u25CB  \u25CB  \u25CB  \u25CB |\nhere   ---|---------------------------------|---\n         1| 2  3  4  5  6  7  8  9  10 11 12|13\n                  \u2191           \u2191        \u2191\n                  lo          mi       hi\n```\n\nNow, if we want to scan this range from left (2) to right (limit\\*2), and we know the maximum number of moves we can make is 2 (replace both numbers). We can transfer the diagram into below:\n```text\n       ---|-------------------------------\u25B2-|---\nmax moves | \u25CB  \u25CB  \u25BC              \u25B2        \u25CB |\n          | \u25CB  \u25CB  \u25CB  \u25CB  \u25CB  \u25CB  \u25BC  \u25CB  \u25CB  \u25CB  \u25CB |\n       ---|---------------------------------|---\n         1| 2  3  4  5  6  7  8  9  10 11 12|13\n                  \u2191           \u2191        \u2191\n                  lo          mi       hi\n```\n\n**The black arrows `\u25BC`(-1) and `\u25B2`(+1) are what we need to take care.**\nNow we can further simplify the diagram as:\n```text\n          |       \u25BC           \u25BC  \u25B2        \u25B2 |\n       ---|---------------------------------|---\n         1| 2  3  4  5  6  7  8  9  10 11 12|13\n                  \u2191           \u2191  \u2191     \u2191  \u2191\n                  lo          mi mi+1  hi hi+1\n```\n\nOK. Now let\'s look at another pair of numbers `(2, 3)` and limit is still `6`\n- oneMoveMin (`l2`) = 2 + (1) = 3\n- oneMoveMax (`h2`) = (6) + 3 = 9\n- justGood (`m2`) = 2 + 3 = 5\n\nWe can make the diagram\n```text\n       ---|-------------------------\u25B2-------|---\nmax moves | \u25CB  \u25BC        \u25B2           \u25CB  \u25CB  \u25CB |\n          | \u25CB  \u25CB  \u25CB  \u25BC  \u25CB  \u25CB  \u25CB  \u25CB  \u25CB  \u25CB  \u25CB |\n       ---|---------------------------------|---\n         1| 2  3  4  5  6  7  8  9  10 11 12|13\n               \u2191     \u2191           \u2191\n               l2    m2          h2\n\n                \u21D3          \u21D3          \u21D3\n                                \n          |    \u25BC     \u25BC  \u25B2           \u25B2       |\n       ---|---------------------------------|---\n         1| 2  3  4  5  6  7  8  9  10 11 12|13\n               \u2191     \u2191  \u2191        \u2191  \u2191\n               l2    m2 m2+1     h2 h2+1\n```\n\nFinally, let\'s look at the array `[3, 2, 1, 2, 3, 5]` and limit `6`.\nThis is essentially the combination of pairs `[3, 5]` `[2, 3]` `[1, 2]` (the first 2 pairs are just examples above)\nWe simply combine the diagrams we got from previous steps:\n```text\n        [3,5] |          \u25BC               \u25BC   \u25B2           \u25B2  |\n        [2,3] |      \u25BC       \u25BC   \u25B2               \u25B2          |\n        [1,2] |  \u25BC   \u25BC   \u25B2                   \u25B2              |\n           ---|---------------------------------------------|---\n[3,2,1,2,3,5] |  \u25BC   \u25BC\u25BC  \u25BC\u25B2  \u25BC   \u25B2       \u25BC   \u25B2\u25B2  \u25B2       \u25B2  |\n           ---|---------------------------------------------|---\nprefix-sum(0) | -1  -3  -3  -4  -3  -3  -4  -2  -1  -1   0  | (starts with 0)\nprefix-sum(6) |  5   3   3   2   3   3   2   4   5   5   6  | (starts with 6)\n           ---|---------------------------------------------|---\n             1|  2   3   4   5   6   7   8   9   10  11  12 |13\n```\n\nWe know the maximum number of moves we can do is 6 (all numbers)\n**Result: the minimum moves required to get `5` or `8` is:** (you can do either)\n- `6 + (-4) = 2` (starts with `0`)\n- `2` (starts with `limit`)\n\n## Implementation\n\n### Step 1 - build the array\n\n```\narray memo(size=(limit*2 + 2), initialValue=(0))\nfor (i from 0 to size(nums)/2-1) do\n    l = ith number of nums\n    r = ith number from the right hand side of nums\n    memo[min(l, r) + 1] -= 1\n    memo[l + r] -= 1\n    memo[l + r + 1] += 1\n    memo[max(l, r) + limit + 1] += 1\nend for\n```\n\nNote: size of the array `memo` is `limit*2 + 2`. Slot 0 is placeholder, and 1 cannot be reached. We use slot `2`~`limit*2`, and we use an extra slot to keep the calculation smooth. Because it is possible that `max(l, r) + limit + 1` and/or `l + r + 1` goes beyond the `limit*2` boundary. It\'s not a must though since we don\'t care about the value.\n\n### Step 2 - calculate the result\n\n```\nans = MAX\ncurr = 0\nfor (i from 2 to limit*2) do\n    curr += memo[i]\n    ans = min(ans, size(nums) + curr)\nend for\n```\n\nOr, below works the same\n\n```\nans = MAX\ncurr = size(nums)\nfor (i from 2 to limit*2) do\n    curr += memo[i]\n    ans = min(ans, curr)\nend for\n```\n\n### Sample code in C++\n\n```cpp\nint minMoves(vector<int>& nums, int limit) {\n    int N = nums.size();\n    vector<int> memo(limit*2 + 2, 0);\n    for (int i = 0; i < N/2; ++i) {\n        int l = nums[i], r = nums[N-1-i];\n        --memo[min(l, r) + 1];\n        --memo[l + r];\n        ++memo[l + r + 1];\n        ++memo[max(l, r) + limit + 1];\n    }\n    int ans = N, curr = N;\n    for (int i = 2; i <= limit*2; ++i) {\n        curr += memo[i];\n        ans = min(ans, curr);\n    }\n    return ans;\n}\n```\n\n## Complexity\n\nTime: O(n + limit)\nspace: O(limit)\n
[]