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

  • \(1 \leq N \leq 2 \times 10^5\)
  • \(0 \leq X \leq10^6\)
  • \(-10^6 \leq Arr[i] \leq 10^6\)

 

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 \(5 - 2 = 3\). The minimum answer is \(3\).

Editor Image

?