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 1:
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.
Example 2:
Input: nums = [1,2,2,1], limit = 2 Output: 2 Explanation: In 2 moves, you can change nums to [2,2,2,2]. You cannot change any number to 3 since 3 > limit.
Example 3:
Input: nums = [1,2,1,2], limit = 2 Output: 0 Explanation: nums is already complementary.
Constraints:
n == nums.length2 <= n <= 1051 <= nums[i] <= limit <= 105nis even.
Solutions
Solution 1: Difference Array
Assume that in the final array, the sum of the pair nums[i] and nums[n-i-1] is s.
Let's denote x as the smaller value between nums[i] and nums[n-i-1], and y as the larger value.
For each pair of numbers, we have the following scenarios:
- If no replacement is needed, then x + y = s.
- If one replacement is made, then x + 1 \le s \le y + limit.
- If two replacements are made, then 2 \le s \le x or y + limit + 1 \le s \le 2 × limit.
That is:
- In the range [2,..x], 2 replacements are needed.
- In the range [x+1,..x+y-1], 1 replacement is needed.
- At [x+y], no replacement is needed.
- In the range [x+y+1,..y + limit], 1 replacement is needed.
- In the range [y + limit + 1,..2 × limit], 2 replacements are needed.
We enumerate each pair of numbers and use a difference array to update the number of replacements needed in different ranges for each pair.
Finally, we find the minimum value among the prefix sums from index 2 to 2 × limit, which is the minimum number of replacements needed.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Similar problems:
class Solution: def minMoves(self, nums: List[int], limit: int) -> int: d = [0] * (2 * limit + 2) n = len(nums) for i in range(n // 2): x, y = nums[i], nums[-i - 1] if x > y: x, y = y, x d[2] += 2 d[x + 1] -= 2 d[x + 1] += 1 d[x + y] -= 1 d[x + y + 1] += 1 d[y + limit + 1] -= 1 d[y + limit + 1] += 2 return min(accumulate(d[2:]))(code-box)
