Minimum (increment by k) operations to make all elements equal
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:
- We Sort the array
- We take the difference of any two elements and this difference should be divisible by k.
- If so, then the elements can become equal with increment in value by K else they cannot be equal.
- 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.