Rust/Python linear solution with explanation
Intuition\n\nLet\'s look at the pair of numbers num[i] and nums[n - i - 1] which are A and B. Now lets look at their sum with respect to the sum S we want to ac
# Intuition\n\nLet\'s look at the pair of numbers `num[i]` and `nums[n - i - 1]` which are `A` and `B`. Now lets look at their sum with respect to the sum `S` we want to achieve and look at all possible ways that can happen. As the order does not matter here, lets assume that `A <= B`. We have the following options:\n\n 1. decrease both\n 2. increase both\n 3. increase smaller, decrease bigger\n 4. increase bigger, decrease smaller\n 5. decrease smaller\n 6. decrease bigger\n 7. increase smaller\n 8. increase bigger\n 9. do not do anything\n \nBut once you look at those situation, you see that some of them do not make sense. For example 2 and 3 as you can just change only one value. There is no reason to decrease smaller value as you would rather do the same with biggger and have more chances to fit into `limit`. Same for increasing bigger. \n\n\nSo you end up with 4 options:\n\n 1. decrease both\n 2. increase both\n 3. decrease bigger\n 4. increase bigger\n\nAnd for this options let check which `S` it can cover.\n\n - `2 <= S < A + 1`. For example lets assume S = 4, A = 5, B = 6. In this case you need to decrease both values.\n - `B + limit < S <= 2 * limit`. For example A = 3, B = 5, S = 13 and limit = 7. In this case you need to increase both values\n - `A + 1 <= S < A + B`. For example A = 5, B = 9, S = 6. Decrease bigger value\n - `A + B < S <= B + limit`. A = 7, B = 9, S = 17, limit = 9. Increase the smaller\n\n\nNow for every pair you need to check which region of S it covers and add increase all the values in that ragion by the number of chanes you need to do. But this is $O(n)$ operation if you increase the range from `x` to `y` by `v`, you can store the array of difference and change `arr[x] += v` and `arr[y] -= v`\n\nWhich gives you those update:\n\n```\narr[2] += 2;\narr[a.min(b) + 1] -= 1;\narr[a + b] -= 1;\narr[a + b + 1] += 1;\narr[a.max(b) + limit + 1] += 1;\n```\n \n\n# Complexity\n\n- Time complexity: $O(n + limit)$\n- Space complexity: $O(limit)$\n\n# Code\n```Rust []\nimpl Solution {\n  pub fn min_moves(nums: Vec<i32>, limit: i32) -> i32 {\n    let limit = limit as usize;\n    let n = nums.len();\n    let mut arr = vec![0; 2 * limit + 2];\n\n    for i in 0 .. n / 2 {\n      let (a, b) = (nums[i] as usize, nums[n - i - 1] as usize);\n      arr[2] += 2;\n      arr[a.min(b) + 1] -= 1;\n      arr[a + b] -= 1;\n      arr[a + b + 1] += 1;\n      arr[a.max(b) + limit + 1] += 1;\n    }\n\n    let (mut res, mut curr) = (i32::MAX, 0);\n    for i in 2 .. arr.len() {\n      curr += arr[i];\n      if curr < res {\n        res = curr;\n      }\n    }\n    \n    return res\n  }\n}\n```\n```python []\nclass Solution:\n  def minMoves(self, nums: List[int], limit: int) -> int:\n    arr = [0] * (2 * limit + 2)\n    for i in range(len(nums) // 2):\n      a, b = nums[i], nums[len(nums) - i - 1]\n      arr[2] += 2\n      arr[min(a, b) + 1] -= 1\n      arr[a + b] -= 1\n      arr[a + b + 1] += 1\n      arr[max(a, b) + limit + 1] += 1\n    \n    res, curr = float(\'inf\'), 0\n    for i in range(2, len(arr)):\n      curr += arr[i]\n      res = min(res, curr)\n    \n    return res\n```\n```ruby []\nputs \'Hello world!\'\n```\n
['Python', 'Rust']