Algorithm

B. Make Them Equal
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/1154/problem/B
input
standard input
output
standard output

You are given a sequence a1,a2,…,an�1,�2,…,�� consisting of n� integers.

You can choose any non-negative integer D� (i.e. D≥0�≥0), and for each ai�� you can:

  • add D� (only once), i. e. perform ai:=ai+D��:=��+�, or
  • subtract D� (only once), i. e. perform ai:=ai−D��:=��−�, or
  • leave the value of ai�� unchanged.

It is possible that after an operation the value ai�� becomes negative.

Your goal is to choose such minimum non-negative integer D� and perform changes in such a way, that all ai�� are equal (i.e. a1=a2=⋯=an�1=�2=⋯=��).

Print the required D� or, if it is impossible to choose such value D�, print -1.

For example, for array [2,8][2,8] the value D=3�=3 is minimum possible because you can obtain the array [5,5][5,5] if you will add D� to 22 and subtract D� from 88. And for array [1,4,7,7][1,4,7,7] the value D=3�=3 is also minimum possible. You can add it to 11 and subtract it from 77 and obtain the array [4,4,4,4][4,4,4,4].

Input

The first line of the input contains one integer n� (1≤n≤1001≤�≤100) — the number of elements in a�.

The second line of the input contains n� integers a1,a2,…,an�1,�2,…,�� (1≤ai≤1001≤��≤100) — the sequence a�.

Output

Print one integer — the minimum non-negative integer value D� such that if you add this value to some ai��, subtract this value from some ai�� and leave some ai�� without changes, all obtained values become equal.

If it is impossible to choose such value D�, print -1.

Examples
input
Copy
6
1 4 4 7 4 1
output
Copy
3
input
Copy
5
2 2 5 2 5
output
Copy
3
input
Copy
4
1 3 3 7
output
Copy
-1
input
Copy
2
2 8
output
Copy
3

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 1e2 + 10;
int n, a[N];
set<int> nums, diffs;

int main() {
  scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    scanf("%d", a + i), nums.insert(a[i]);
  sort(a, a + n);
  for(int i = 1; i < n; ++i) {
    if(a[i] - a[i-1] == 0)
      continue;
    diffs.insert(a[i] - a[i-1]);
  }
  
  if(nums.size() == 1) {
    puts("0");
  } else if(nums.size() == 2) {
    if((*diffs.begin()) % 2 == 0)
      printf("%d\n", (*diffs.begin()) / 2);
    else
      printf("%d\n", (*diffs.begin()));
  } else if(nums.size() == 3 && diffs.size() == 1) {
    printf("%d\n", (*diffs.begin()));
  } else {
    puts("-1");
  }

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
6
1 4 4 7 4 1

Output

x
–
+
cmd
3
Advertisements

Demonstration

Codeforces Solution-Make Them Equal--Solution in C, C++, Java, Python ,Codeforces Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+