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 otherint 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 modulosint 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 Codeint 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 approachimport java.util.*;class GFG{ // Function to find the minimum operations// required to make the modulo of each// element of the array equal to each otherstatic 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 modulosstatic 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 Codepublic 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 approachimport sysfrom collections import defaultdict# Function to find the minimum operations# required to make the modulo of each# element of the array equal to each otherdef 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 modulosdef 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 Codeif __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 approachusing 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 otherstatic 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 modulosstatic 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 Codepublic 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 otherfunction 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 modulosfunction 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 Codelet 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:
2
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
