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:

  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.