# Minimum (increment by k) operations to make all elements equal

Get FREE domain for 1st year and build your brand new site Given an array arr[] of N elements and an integer K, we have to perform increment operation on the array values such that every element inside the arrray becomes equal. An operation can increase value of an element by K. If impossible to make all the elements inside the array equal print -1.

This is a modification of this problem where we increment by 1 and make only K elements equal. Go through this problem as well.

EXAMPLES

``````Input : arr[] = {4, 7, 19, 16}, k = 3
Output : 8

Input : arr[] = {4, 2, 6, 8}, k = 3
Output : -1
``````

To solve this question we have to check whether each and every element inside the array can became equal or not with the given condition incrementing value by k from every element's value.

Solution

The steps to solve the problem are as follows:

1. We Sort the array
2. We take the difference of any two elements and this difference should be divisible by k.
3. If so, then the elements can become equal with increment in value by K else they cannot be equal.
4. Number of operations required in the process is calculated by (max – arr(i))/k for all elements in the array. max being maximum element in the array (can be found out by sorting the array).

Pseudocode

``````// iterating for all elements in the array
for (int i=0; i<n; i++)
{
// checking if element can be equal to maximum element
//or not, if no then return -1
if ((max - arr[i]) % k != 0 )
return -1;

// else update res for required operations
else
res += (max - arr[i]) / k ;
}

return res;
``````

Code(JAVA)

``````//JAVA solution
import java.util.*;
import java.io.*;

class Solution {
// Driver program
public static void main(String[] args)
{
int arr[] = { 4, 7, 19, 16 };
int n = arr.length;
int k = 3;

// finding the max element in array

Arrays.sort(arr);
int maximum = arr[arr.length - 1];
int result = 0;

//To keep track of possible to make array
//elements equal or not

boolean flag=true;
// iterate for all elements
for (int j = 0; j < n; j++) {

// checking element can be equal to
// max, if not make flag false;
if ((maximum - arr[j]) % k != 0) {
flag=false;
break;
}

// else update res for required operations
else
result += (maximum - arr[i]) / k;
}

//flag true

if(flag==true){
System.out.println(result);
}

//else flag is false
//array elements cannot be equal

else{
System.out.println("-1");
}
}
}
``````
``````Output: 8
``````

As we have to sort the array so Time complexity required in this algorithm is O(N logN) and we don't require any extra space so Space complexity is O(1).

Therefore:

• Time Complexity: O(N logN)
• Space Complexity: O(1)

With this article at OpenGenus, you must have the complete idea of finding the minimum number of (increment by k) operations to make all elements equal.