Closer

4.3

3 votes
Basics of Greedy Algorithms, Algorithms, Greedy Algorithms
Problem

You are given an array A of N integers. You can perform following operations :

  • Choose two distinct indices i and j, increment Ai by 1 and decrement Aj by 1

Find the minimum number of operations you should perform such that absolute difference between any two elements is at most K 

 

Input Format:

The First line contains two integers N and K .

The second line contains the N elements of array A .

 

Output Format

Print the minimum number of operations.

 

Constraints

1N1051K1091Ai105

Sample Input
4 3 
1 5 1 10
Sample Output
4
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In first operation we choose i=1 and j=4 so  A = [2,5,1,9]

In second operation we choose i=3 and j=4 so  A = [2,5,2,8]

In third operation we choose i=1 and j=4 so  A = [3,5,2,7]

In fourth operation we choose i=3 and j=4 so  A = [3,5,3,6]

Editor Image

?