Minimum increment by k operations to make all equal

Try it on GfG Practice

You are given an array of n-elements, you have to find the number of operations needed to make all elements of array equal. Where a single operation can increment an element by k. If it is not possible to make all elements equal print -1.

Example : 

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

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

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

To solve this question we require to check whether all elements can became equal or not and that too only by incrementing k from elements value. For this we have to check that the difference of any two elements should always be divisible by k. If it is so, then all elements can become equal otherwise they can not became equal in any case by incrementing k from them. Also, the number of operations required can be calculated by finding value of (max - Ai)/k for all elements. where max is maximum element of array.

Algorithm : 

// iterate for all elements
for (int i=0; i<n; i++)
{
// check if element can make equal to max
// or not if not 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;

#include <bits/stdc++.h>
using namespace std;

int minOps(vector<int>& arr, int k) {
  
    int maxVal = *max_element(arr.begin(), arr.end());
    int res = 0;

    for (int x : arr) {
      
        // check if element can be made equal to max
        // if not, return -1
        if ((maxVal - x) % k != 0)
            return -1;

        // else, update res for required operations
        res += (maxVal - x) / k;
    }

    return res;
}

int main() {
    vector<int> arr = { 21, 33, 9, 45, 63 };
    int k = 6;

    cout << minOps(arr, k);
    return 0;
}

// Program to make all array equal
import java.io.*;
import java.util.Arrays;

class GFG {
    // function for calculating min operations
    static int minOps(int arr[], int n, int k)
    {
        // max elements of array
        int max = Integer.MIN_VALUE;
          for(int i=0; i<n; i++) {
            max = Math.max(max, arr[i]);
        }
        int res = 0;

        // iterate for all elements
        for (int i = 0; i < n; i++) {

            // check if element can make equal to
            // max or not if not then return -1
            if ((max - arr[i]) % k != 0)
                return -1;

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

        // return result
        return res;
    }

    // Driver program
    public static void main(String[] args)
    {
        int arr[] = { 21, 33, 9, 45, 63 };
        int n = arr.length;
        int k = 6;
        System.out.println(minOps(arr, n, k));
    }
}

// This code is contributed by vt_m

# Python3 Program to make all array equal

# function for calculating min operations
def minOps(arr, n, k):

    # max elements of array
    max1 = max(arr)
    res = 0

    # iterate for all elements
    for i in range(0, n): 

        # check if element can make equal to
        # max or not if not then return -1
        if ((max1 - arr[i]) % k != 0):
            return -1

        # else update res for
        # required operations
        else:
            res += (max1 - arr[i]) / k
    
    # return result
    return int(res)

# driver program
arr = [21, 33, 9, 45, 63] 
n = len(arr)
k = 6
print(minOps(arr, n, k))

# This code is contributed by 
# Smitha Dinesh Semwal

// C# program Minimum increment by
// k operations to make all elements equal.
using System;

class GFG {
    
    // function for calculating min operations
    static int minOps(int[] arr, int n, int k)
    {
        
        // max elements of array
        Array.Sort(arr);
        int max = arr[arr.Length - 1];
        int res = 0;

        // iterate for all elements
        for (int i = 0; i < n; i++) {

            // check if element can make
            // equal to max or not if not
            // then return -1
            if ((max - arr[i]) % k != 0)
                return -1;

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

        // return result
        return res;
    }

    // Driver program
    public static void Main()
    {
        int[] arr = { 21, 33, 9, 45, 63 };
        int n = arr.Length;
        int k = 6;

        Console.Write(minOps(arr, n, k));
    }
}

// This code is contributed by nitin mittal.

<script>

// Program to make all array equal

// function for calculating min operations
function minOps(arr, n, k)
{
    // max elements of array
    var max = arr[0];
    
    for(var i=0; i<arr.length; i++)
    {
        if(arr[i]>max)
            max = arr[i];
    }
    var res = 0;

    // iterate for all elements
    for (var i = 0; i < n; i++) {

        // check if element can make equal to
        // max or not if not then return -1
        if ((max - arr[i]) % k != 0)
            return -1;

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

    // return result
    return res;
}

// driver program
var arr = [ 21, 33, 9, 45, 63 ];
var n = arr.length;
var k = 6;
document.write( minOps(arr, n, k));

// This code is contributed by rutvik_56.
</script>    

<?php
// Program to make all array equal

// function for calculating 
// min operations
function minOps($arr, $n, $k)
{
    // max elements of array
    $max = max($arr);
    $res = 0;

    // iterate for all elements
    for ($i = 0; $i < $n; $i++) 
    {

        // check if element can 
        // make equal to max or
        // not if not then return -1
        if (($max - $arr[$i]) % $k != 0)
            return -1;

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

// Driver Code
$arr = array(21, 33, 9, 45, 63);
$n = count($arr);
$k = 6;
print (minOps($arr, $n, $k));

// This code is contributed 
// by Manish Shaw(manishshaw1)
?>

24

Time Complexity: O(n)
Auxiliary Space: O(1)