Operation with X

4

21 votes
Algorithms, Sorting, Greedy Algorithms, Basics of Greedy Algorithms
Problem

We have an array Arr of N integer points and an integer X. At each element Arr[i], we will either add X or subtract X. We have to operate in such a way, that the absolute difference between the maximum value and the minimum value in the array is minimal.

Find the minimum absolute difference between the maximum value obtained by the operation.

Input format

  • The first line contains two space-separated integers N and X, where N denotes the size of the array Arr.
  • The second line contains N space-separated integers denoting array Arr.

Output format

Print the minimum value obtained by the operation.

Constraints

  • 1N2×105
  • 0X106
  • 106Arr[i]106

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

We can add X to the 2,3,0 and subtract X from 5 to get [4,5,2,3]. The absolute difference between the maximum and minimum element is 52=3. The minimum answer is 3.

Editor Image

?