Minimum number of operations to make pair sums of array equal

I think the following should work:

• iterate pairs of numbers
• for each pair, calculate the sum of that pair, as well as the min and max sum that can be achieved by changing just one of the values
• update a dictionary/map with -1 when starting a new "region" requiring one fewer change, and +1 when that region is over
• iterate the boundaries in that dictionary and update the total changes needed to find the sum that requires the fewest updates

Example code in Python, giving 9 as the best sum for your example, requiring 5 changes.

from collections import defaultdict

nums = [10, 7, 2, 9, 4, 1, 7, 3, 10, 8]
m = max(nums)
pairs = [(nums[i], nums[-1-i]) for i in range(len(nums)//2)]
print(pairs)

score = defaultdict(int)
for a, b in map(sorted, pairs):
    low = a + 1
    high = m + b
    score[low] -= 1
    score[a+b] -= 1
    score[a+b+1] += 1
    score[high+1] += 1
print(sorted(score.items()))

cur = best = len(nums)
num = None
for i in sorted(score):
    cur += score[i]
    print(i, cur)
    if cur < best:
        best, num = cur, i
print(best, num)

The total complexity of this should be O(nlogn), needing O(n) to create the dictionary, O(nlogn) for sorting, and O(n) for iterating the sorted values in that dictionary. (Do not use an array or the complexity could be much higher if max(nums) >> len(nums))

(UPDATED receiving additional information)

The optimal sum must be one of the following:

• a sum of a pair -> because you can keep both numbers of that pair
• the min value of a pair + 1 -> because it is the smallest possible sum you only need to change 1 of the numbers for that pair
• the max value of a pair + the max overall value -> because it is the largest possible sum you only need to change 1 of the numbers for that pair

Hence, there are order N possible sums.

The total number of operations for this optimal sum can be calculated in various ways.

The O(N²) is quite trivial. And you can implement it quite easily if you want to confirm other solutions work.

Making it O(N log N)

• getting all possible optimal sums O(N)
• for each possible sum you can calculate occ the number of pairs having that exact sum and thus don't require any manipulation. O(N)
• For all other pairs you just need to know if it requires 1 or 2 operations to get to that sum. Which is 2 when it is either impossible if the smallest of the pair is too big to reach sum with the smallest possible number or when the largest of the pair is too small to reach the sum with the largest possible number. Many data structures could be used for that (BIT, Tree, ..). I just used a sorted list and applied binary search (not exhaustively tested though). O(N log N)

Example solution in java:

int[] nums = new int[] {10, 7, 2, 9, 4, 1, 7, 3, 10, 8};
// preprocess pairs: O(N)
int min = 1
    , max = nums[0];
List<Integer> minList = new ArrayList<>();
List<Integer> maxList = new ArrayList<>();
Map<Integer, Integer> occ = new HashMap<>();
for (int i=0;i<nums.length/2;i++) {
    int curMin = Math.min(nums[i], nums[nums.length-1-i]);
    int curMax = Math.max(nums[i], nums[nums.length-1-i]);
    min = Math.min(min, curMin);
    max = Math.max(max, curMax);
    minList.add(curMin);
    maxList.add(curMax);
    // create all pair sums
    int pairSum = nums[i] + nums[nums.length-1-i];
    int currentOccurences = occ.getOrDefault(pairSum, 0);
    occ.put(pairSum, currentOccurences + 1);
}
// sorting 0(N log N)
Collections.sort(minList);
Collections.sort(maxList);
// border cases 
for (int a : minList) {
    occ.putIfAbsent(a + max, 0);
}
for (int a : maxList) {
    occ.putIfAbsent(a + min, 0);
}

// loop over all condidates O(N log N)
int best = (nums.length-2);
int med = max + min;
for (Map.Entry<Integer, Integer> entry : occ.entrySet()) {
    int sum = entry.getKey();
    int count = entry.getValue();
    int requiredChanges = (nums.length / 2) - count;
    if (sum > med) {
        // border case where max of pair is too small to be changed to pair of sum
        requiredChanges += countSmaller(maxList, sum - max);
    } else if (sum < med) {
        // border case where having a min of pair is too big to be changed to pair of sum
        requiredChanges += countGreater(minList, sum - min);
    }
    System.out.println(sum + " -> " + requiredChanges);
    best = Math.min(best, requiredChanges);
}
System.out.println("Result: " + best);
}

// O(log N)
private static int countGreater(List<Integer> list, int key) {
 int low=0, high=list.size();
 while(low < high) {
     int mid = (low + high) / 2;
     if (list.get(mid) <= key) {
        low = mid + 1;
    } else {
        high = mid;
    }
 }
 return list.size() - low;
}

// O(log N)
private static int countSmaller(List<Integer> list, int key) {
 int low=0, high=list.size();
 while(low < high) {
     int mid = (low + high) / 2;
     if (list.get(mid) < key) {
        low = mid + 1;
    } else {
        high = mid;
    }
 }
 return low;
}

Just to offer some theory -- we can easily show that the upper bound for needed changes is n / 2, where n is the number of elements. This is because each pair can be made in one change to anything between 1 + C and max(nums) + C, where C is any of the two elements in a pair. For the smallest C, we can bind max(nums) + 1 at the highest; and for the largest C, we can bind 1 + max(nums) at the lowest.

Since those two bounds at the worst cases are equal, we are guaranteed there is some solution with at most N / 2 changes that leaves at least one C (array element) unchanged.

From that we conclude that an optimal solution either (1) has at least one pair where neither element is changed and the rest require only one change per pair, or (2) our optimal solution has n / 2 changes as discussed above.

We can therefore proceed to test each existing pair's single or zero change possibilities as candidates. We can iterate over a sorted list of two to three possibilities per pair, labeled with each cost and index. (Other authors on this page have offered similar ways and code.)