Minimize increment/decrement of Array elements to make each modulo K equal

0 0 8 minutes read

Given an array arr[] of length N and an integer K. In each operation any element(say arr[i]) can be selected from the array and can be changed to arr[i] + 1 or arr[i] – 1. The task is to find the minimum number of operations required to perform on the array such that each value of the array modulo K remains the same.

Examples:

Input: arr[] = {4, 5, 8, 3, 12}, k =5
Output: 4
Explanation:
Operation 1: { 3, 5, 8, 3, 12 }, decrease 4 at index 0 by 1.
Operation 2: { 3, 4, 8, 3, 12 }, decrease 5 at index 1 by 1.
Operation 3: { 3, 3, 8, 3, 12 }, decrease 4 at index 1 by 1.
Operation 4: { 3, 3, 8, 3, 13 }, increase 12 at index 4 by 1.
The modulo of each number is equal to 3 and minimum steps required were 4.

Input: arr[] = {2, 35, 48, 23, 52}, k =3
Output: 2
Explanation:
Minimum number of steps required to make modulo of each number equal is 2.

Approach: The idea is to use Hashing that keeps the count of each modulo that has been obtained.

Now iterate for each value of i, in range 0 <= i < k, and find the number of operation required to make the modulo of all numbers equal.
If it is less than the value obtained than the currently stored value then update it.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum operations
// required to make the modulo of each
// element of the array equal to each other
int Find_min(set<int>& diff_mod,
             map<int, int> count_mod, int k)
{
    // Variable to store minimum
    // operation required
    int min_oprn = INT_MAX;
 
    // To store operation required to
    // make all modulo equal
    int oprn = 0;
 
    // Iterating through all
    // possible modulo value
    for (int x = 0; x < k; x++) {
        oprn = 0;
 
        // Iterating through all different
        // modulo obtained so far
        for (auto w : diff_mod) {
 
            // Calculating oprn required
            // to make all modulos equal
            // to x
            if (w != x) {
 
                if (w == 0) {
 
                    // Checking the operations
                    // that will cost less
                    oprn += min(x, k - x)
                            * count_mod[w];
                }
 
                else {
 
                    // Check operation that
                    // will cost less
                    oprn += min(
                                abs(x - w),
                                k + x - w)
                            * count_mod[w];
                }
            }
        }
 
        // Update the minimum
        // number of operations
        if (oprn < min_oprn)
            min_oprn = oprn;
    }
 
    // Returning the answer
    return min_oprn;
}
 
// Function to store different modulos
int Cal_min(int arr[], int n, int k)
{
    // Set to store all
    // different modulo
    set<int> diff_mod;
 
    // Map to store count
    // of all different  modulo
    // obtained
    map<int, int> count_mod;
 
    // Storing all different
    // modulo count
    for (int i = 0; i < n; i++) {
 
        // Insert into the set
        diff_mod.insert(arr[i] % k);
 
        // Increment count
        count_mod[arr[i] % k]++;
    }
 
    // Function call to return value of
    // min oprn required
    return Find_min(diff_mod, count_mod, k);
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 35, 48, 23, 52 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << Cal_min(arr, n, k);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to find the minimum operations
// required to make the modulo of each
// element of the array equal to each other
static int Find_min(HashSet<Integer> diff_mod,
                    HashMap<Integer, 
                            Integer> count_mod,
                    int k)
{
     
    // Variable to store minimum
    // operation required
    int min_oprn = Integer.MAX_VALUE;
 
    // To store operation required to
    // make all modulo equal
    int oprn = 0;
 
    // Iterating through all
    // possible modulo value
    for(int x = 0; x < k; x++)
    {
        oprn = 0;
 
        // Iterating through all different
        // modulo obtained so far
        for(int w : diff_mod) 
        {
 
            // Calculating oprn required
            // to make all modulos equal
            // to x
            if (w != x) 
            {
                if (w == 0)
                {
                     
                    // Checking the operations
                    // that will cost less
                    oprn += Math.min(x, k - x) *
                            count_mod.get(w);
                }
                else
                {
                     
                    // Check operation that
                    // will cost less
                    oprn += Math.min(Math.abs(x - w), 
                                     k + x - w) * 
                                     count_mod.get(w);
                }
            }
        }
 
        // Update the minimum
        // number of operations
        if (oprn < min_oprn)
            min_oprn = oprn;
    }
 
    // Returning the answer
    return min_oprn;
}
 
// Function to store different modulos
static int Cal_min(int arr[], int n, int k)
{
     
    // Set to store all
    // different modulo
    HashSet<Integer> diff_mod = new HashSet<>();
 
    // Map to store count
    // of all different modulo
    // obtained
    HashMap<Integer, 
            Integer> count_mod = new HashMap<>();
 
    // Storing all different
    // modulo count
    for(int i = 0; i < n; i++) 
    {
         
        // Insert into the set
        diff_mod.add(arr[i] % k);
 
        // Increment count
        count_mod.put(arr[i] % k, 
        count_mod.getOrDefault(arr[i] % k, 0) + 1);
    }
 
    // Function call to return value of
    // min oprn required
    return Find_min(diff_mod, count_mod, k);
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 2, 35, 48, 23, 52 };
    int n = arr.length;
    int k = 3;
     
    System.out.print(Cal_min(arr, n, k));
}
}
 
// This code is contributed by jrishabh99

Python3

# Python3 program for 
# the above approach
import sys
from collections import defaultdict
 
# Function to find the minimum operations
# required to make the modulo of each
# element of the array equal to each other
def Find_min(diff_mod,
             count_mod, k):
 
    # Variable to store minimum
    # operation required
    min_oprn = sys.maxsize
 
    # To store operation required to
    # make all modulo equal
    oprn = 0
 
    # Iterating through all
    # possible modulo value
    for x in range (k):
        oprn = 0
 
        # Iterating through all different
        # modulo obtained so far
        for w in diff_mod:
 
            # Calculating oprn required
            # to make all modulos equal
            # to x
            if (w != x):
 
                if (w == 0):
 
                    # Checking the operations
                    # that will cost less
                    oprn += (min(x, k - x) *
                             count_mod[w])
                
                else:
 
                    # Check operation that
                    # will cost less
                    oprn += (min(abs(x - w), 
                                     k + x - w) *
                                     count_mod[w])
           
        # Update the minimum
        # number of operations
        if (oprn < min_oprn):
            min_oprn = oprn
    
    # Returning the answer
    return min_oprn
 
# Function to store different modulos
def Cal_min(arr,  n, k):
 
    # Set to store all
    # different modulo
    diff_mod = set([])
 
    # Map to store count
    # of all different  modulo
    # obtained
    count_mod = defaultdict (int)
 
    # Storing all different
    # modulo count
    for i in range (n):
 
        # Insert into the set
        diff_mod.add(arr[i] % k)
 
        # Increment count
        count_mod[arr[i] % k] += 1
    
    # Function call to return value of
    # min oprn required
    return Find_min(diff_mod, count_mod, k)
 
# Driver Code
if __name__ == "__main__":  
    arr = [2, 35, 48, 23, 52]
    n = len(arr)
    k = 3
    print( Cal_min(arr, n, k))
     
# This code is contributed by Chitranayal

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to find the minimum operations
// required to make the modulo of each
// element of the array equal to each other
static int Find_min(HashSet<int> diff_mod,
                    Dictionary<int, 
                               int> count_mod,
                    int k)
{
     
    // Variable to store minimum
    // operation required
    int min_oprn = int.MaxValue;
 
    // To store operation required to
    // make all modulo equal
    int oprn = 0;
 
    // Iterating through all
    // possible modulo value
    for(int x = 0; x < k; x++)
    {
        oprn = 0;
 
        // Iterating through all different
        // modulo obtained so far
        foreach(int w in diff_mod) 
        {
 
            // Calculating oprn required
            // to make all modulos equal
            // to x
            if (w != x) 
            {
                if (w == 0)
                {
                     
                    // Checking the operations
                    // that will cost less
                    oprn += Math.Min(x, k - x) *
                            count_mod[w];
                }
                else
                {
                     
                    // Check operation that
                    // will cost less
                    oprn += Math.Min(Math.Abs(x - w), 
                                     k + x - w) * 
                                     count_mod[w];
                }
            }
        }
 
        // Update the minimum
        // number of operations
        if (oprn < min_oprn)
            min_oprn = oprn;
    }
 
    // Returning the answer
    return min_oprn;
}
 
// Function to store different modulos
static int Cal_min(int []arr, int n, int k)
{
     
    // Set to store all
    // different modulo
    HashSet<int> diff_mod = new HashSet<int>();
 
    // Map to store count
    // of all different modulo
    // obtained
    Dictionary<int, 
               int> count_mod = new Dictionary<int,
                                               int>();
 
    // Storing all different
    // modulo count
    for(int i = 0; i < n; i++) 
    {
         
        // Insert into the set
        diff_mod.Add(arr[i] % k);
 
        // Increment count
        if(count_mod.ContainsKey((arr[i] % k)))
            count_mod[arr[i] % k] = count_mod[(arr[i] % k)]+1;
        else
            count_mod.Add(arr[i] % k, 1);
    }
 
    // Function call to return value of
    // min oprn required
    return Find_min(diff_mod, count_mod, k);
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 2, 35, 48, 23, 52 };
    int n = arr.Length;
    int k = 3;
     
    Console.Write(Cal_min(arr, n, k));
}
}
 
// This code is contributed by Amit Katiyar 

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find the minimum operations
// required to make the modulo of each
// element of the array equal to each other
function Find_min(diff_mod, count_mod, k)
{
     
    // Variable to store minimum
    // operation required
    let min_oprn = Number.MAX_VALUE;
  
    // To store operation required to
    // make all modulo equal
    let oprn = 0;
  
    // Iterating through all
    // possible modulo value
    for(let x = 0; x < k; x++)
    {
        oprn = 0;
         
        // Iterating through all different
        // modulo obtained so far
        for(let w of diff_mod.values())
        {
             
            // Calculating oprn required
            // to make all modulos equal
            // to x
            if (w != x)
            {
                if (w == 0)
                {
                     
                    // Checking the operations
                    // that will cost less
                    oprn += Math.min(x, k - x) *
                            count_mod.get(w);
                }
                else
                {
                     
                    // Check operation that
                    // will cost less
                    oprn += Math.min(Math.abs(x - w),
                                          k + x - w) *
                                    count_mod.get(w);
                }
            }
        }
         
        // Update the minimum
        // number of operations
        if (oprn < min_oprn)
            min_oprn = oprn;
    }
  
    // Returning the answer
    return min_oprn;
}
 
// Function to store different modulos
function Cal_min(arr, n, k)
{
     
    // Set to store all
    // different modulo
    let diff_mod = new Set();
  
    // Map to store count
    // of all different modulo
    // obtained
    let count_mod = new Map();
  
    // Storing all different
    // modulo count
    for(let i = 0; i < n; i++)
    {
          
        // Insert into the set
        diff_mod.add(arr[i] % k);
  
        // Increment count
        // Increment count
        if(count_mod.has((arr[i] % k)))
            count_mod.set(arr[i] % k,
            count_mod.get(arr[i] % k) + 1);
        else
            count_mod.set(arr[i] % k, 1);
     }
  
    // Function call to return value of
    // min oprn required
    return Find_min(diff_mod, count_mod, k);
}
 
// Driver Code
let arr = [ 2, 35, 48, 23, 52 ];
let n = arr.length;
let k = 3;
 
document.write(Cal_min(arr, n, k));
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Output:

Time Complexity: O(N*K), where N is the length of the given array and K is the given value.
Auxiliary Space: O(N+K), where N is the length of the given array and K is the given value.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!