Given an array arr[] of n elements and an integer k, the task is to make any k elements of the array equal by performing only increment operations i.e. in one operation, any element can be incremented by 1.
Find the minimum number of operations required to make any K elements equal.

• Approach1: Naive approach
• Approach2 : Sliding window technique

Approach1: Naive approach

• Sort the array.
• Check the size of array, if it is less than k then return 0, it is not possible to make k elements equal since no. of elements in array are less than k.
• If size of array is greater than or equal to k, then start iterating from index i = 0, and for every arr[i] check elements from arr[i] to arr[i+k-1] and calculate how many increment operations will make them equal to arr[i+k-1] individually and take sum of all increment operations and store it in variable count.
• Do this for all values of i till i< arr.length, minimum value of count out of all counts for every i will be the output.

Example1

Input: arr[] ={1,4,3,20}, k = 3
Output: 4

Explanation:
- After sorting, array becomes arr[] ={1,3,4,20}
- for i =0, i+k-1 = 2, so we have to calculate number of increments needed to make all elements at indices in range [0,2] equals to arr[2].
i.e arr[0] -> arr[2] => 1->4 =>(4-1)= 3 increment operations
arr[1] -> arr[2] => 3->4 => (4-3) = 1 increment operation
arr[2] -> arr[2] => 4->4 =>(4-4) = 0 increment operation
so total increment operations needed are, i.e count1 = 3+1+0 = 4.

- for i=1, i+k-1 = 3, so we have to calculate number of increments needed to make elements at indices in range [1,3] equals to arr[3].
i.e arr[1] -> arr[3] => 3->20 =>(20-3)= 17 increment operations
arr[2] -> arr[3] => 4->20 => (20-4) = 16 increment operation
arr[3] -> arr[3] => 20->20 =>(20-20) = 0 increment operation
so total increment operations needed are, i.e count2 = 17+16 = 33.

- for i=2, i+k-1 = 4, since length of array is 4, element for index 4 does not exist. So itereation ends here.
- count1 = 4, count2 = 33, so minimum of both i.e 4 is the output.

Example2

Input: arr[] ={1,4,3,20}, k=5
Output: 0

Explanation: 
for i=0, i+k-1 = 4, since length of array is 4, element for index 4 does not exist. so it is not possible to make 5 elements all equal.

Code

import java.util.*;
public class solution{
   public static void main( String[] args)
   {
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       int[] arr = new int[n];
       for(int i=0;i<n;i++)
       {
           arr[i] = sc.nextInt();
       }
       int k = sc.nextInt();
       int result = countOperations(arr, k);
       System.out.println(result);
   }
   public static int countOperations(int[] arr, int k)
   {
       Arrays.sort(arr);
       int min = Integer.MAX_VALUE;
       for(int i = 0; i < arr.length; i++)
       {
           int count =0;
           int up = i+k-1;
           int j = i;
           if(up <arr.length)
           {
               while(j<=up )
               {
                   count = count+(arr[up]-arr[j]);
                   j++;
               }
               min = Math.min(min,count);
           }
       }
       if(min == Integer.MAX_VALUE )
           return 0;
       return min;
   }
}

Time Complexity : O(n*K + nlogn)

Approach2 : Sliding window technique

-As in the naive approach, we are calculating number of operation for each k elements subset, we can improve this by using sliding window concept.
What we can do is, when first k elements operation is calculated, we will remove one element from left end and add one element from right side in our window and will update our previously calculated number of operation accoridng to element removed and element added to our window.

• Let count1 be the number of operations needed in first subset of k elements i.e to make all elements at indices in range (i to i+k-1) equal to arr[i+k-1].
• and let count2 be the number of operations needed in second subset of k elements i.e to make all elements at indices in range (i+1 to (i+1)+k-1) equal to arr[i+k].
• But while calculating count2, i.e for the second subset, we can make use of count1, since while calculating count2 only arr[i-1] term is removed and extra term arr[i+k-1] is taken into consideration.
• so we can write count2, in terms of count1 as,
  count2 = count1 - [(arr[i+k-2]-arr[i-1])] + [(arr[i+k-1]-arr[i+k-2])x(k-1)]
• we will calculate number of increment operations need i.e count for each value of i, minimum of all counts will be the output.
  Let us understand this with example,

Example

 Input: arr[] ={1,4,3,20}, k = 3
 
- After sorting arr[] = {1,3,4,20}

- when i = 0, 
 for indices in range(i,i+k-1) i,e (0,2), increment all elements at these indices and make them equal to arr[2].
arr[2] = 4 so, count = (arr[2] -arr[0])+(arr[2] -arr[1])+(arr[2] -arr[2])
=> count = (4-1)+(4-3)+(4-4) = 4

- now when i = 1,
 for indices in range (i,i+k-1) i.e (1,3), to calculate increments required to make all elements in this range equal to arr[3] i.e equal to 20, we can remove the increment operations due to 1(which is at index 0) i.e (4-1 = 3) from the count and can add changes due to taking 20 which is at index 3.
so count = 4-(4-1)+(20-4)x(2)= 33

- when i = 3, i+k-1 becomes out of bound, so iteration terminates here.
minimmum of all count will be the output, minimum of (4,33) is 4, so 4 will be the output.

code

import java.util.*;
public class solution{
    public static void main( String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sc.nextInt();
        }
        int k = sc.nextInt();
        int result = countOperations(arr, k);
        System.out.println(result);
    }
    public static int countOperations(int[] arr, int k)
    {
        if(arr.length < k)
            return 0;
        Arrays.sort(arr);
        int min = Integer.MAX_VALUE;
        int i =0;
        int count = 0;
        while(i<k )
        {
            count = count+(arr[k-1]-arr[i]);
            i++;
        }
        min = Math.min(count,min);
        for( i=1;i<arr.length;i++)
        {
            if(i+k-1 >= arr.length)
                break;
            count = count-(arr[i+k-2]-arr[i-1])     // removing the increment operations due to arr[i-1]
            count = count+(arr[i+k-1]-arr[i+k-2])*(k-1);    // adding extra increment operations needed to make elements equal tp arr[i+k-1]
            min = Math.min(count,min);
        }
        if(min == Integer.MAX_VALUE )
            return 0;
        return min;
    }
}

Time Complexity : O(nlogn)