CodeForces Round 552B. Make them Equal [Analysis]

The problem is to basically find the minimum non-negative integer D such that we can either add D to an element of the array, subtract D from an element of the array, or don’t modify the element at all and make all the elements of the array equal. It’s quite easy to see a brute force solution: we can try out all the possible values of D on the sorted (in ascending) array of inputs. If this is the case for some D all the elements in the array must equal to a[0] + D (i.e. the first element of the sorted array + D).

Because $1 <= a[i] <= 100$ and $1 <= n <= 100$ and the brute force algorithm has time complexity of $O(n^2)$ this code passes all the test cases within the time limit.

#include <iostream>
#include <cstdio>
#include <algorithm> 
using namespace std;
int a[111];
int main(int argc,char **argv){
  int n;
  scanf("%d",&n);
  for (int i = 0; i < n; i++){
    scanf("%d",&a[i]);
  }
  sort(a,a+n);
  for (int d = 0; d <= a[n-1]; d++){
    int target = a[0]+d;
    bool ans = true;
    for (int i = 0; i < n; i++){
      if (a[i] != target && abs(target-a[i]) != d){
        ans = false;
        break;
      }
    }
    if (ans){
      return !printf("%d\n",d);
    }
  }
  puts("-1");
  return 0;
}

However, this is not a very smart solution. What if $n > 10000$? In this case a quadratic solution will not work. We need to come up with something more clever. Suppose we sort the array a and get rid of all the duplicate elements of a (so the array a only contains unique elements). We can actually observe that if $n = 1$, then D = 0 because we don’t have to change anything. If $n = 2$, then we have two possible candidates for D: $(a[1]-a[0])/2$ if $a[1]-a[0]$ is even or $a[1]-a[0]$ if $a[1]-a[0]$ is odd. If $n = 3$ then we can only find a possible value for $D$ if and only if $a[1]-a[0] = a[2]-a[1]$. In this case we can increase a[0] by D and decrease a[2] by $a[1]-a[0]$ so that all the elements would be equal to a[1]. For $n >= 4$ we see that it is not possible to find a suitable D because even if the difference of consecutive elements are equal, there is no way to add some number to each elements of the array to make them all equal to a single value.
This solution has a performance of $O(1)$, which is much better than the above brute force solution.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 111;
bool exist[MAXN];
int main(int argc,char **argv){
  int n,x;
  scanf("%d",&n);
  vector<int> a;
  for (int i = 0; i < n; i++){
    scanf("%d",&x);
    if (!exist[x]){
      exist[x] = true;
      a.push_back(x);
    }
  }
  sort(a.begin(),a.end()); // a only contains distinct values at this point
  if (a.size() >= 4){
    printf("-1\n");
  }else if (a.size() == 3){
    if (a[1]-a[0] == a[2]-a[1]){
      printf("%d\n",a[1]-a[0]);
    }else{
      puts("-1");
    }
  }else if (a.size() == 2){
    if ((a[1]-a[0])%2 == 0){
      printf("%d\n",(a[1]-a[0])/2);
    }else{
      printf("%d\n",a[1]-a[0]);
    }
  }else if (a.size() == 1){
    puts("0");
  }
  return 0;
}