Minimum operations to make counts of remainders same in an array
Given an array arr[] of N integers and an integer M where N % M = 0. The task is to find the minimum number of operations that need to be performed on the array to make c0 = c1 = ….. = cM – 1 = N / M where cr is the number of elements in the given array having remainder r when divided by M. In each operation, any array element can be incremented by 1.
Examples:
Input: arr[] = {1, 2, 3}, M = 3
Output: 0
After performing the modulus operation on the given array, the array becomes {0, 1, 2}
And count of c0 = c1 = c2 = n / m = 1.
So, no any additional operations are required.Input: arr[] = {3, 2, 0, 6, 10, 12}, M = 3
Output: 3
After performing the modulus operation on the given array, the array becomes {0, 2, 0, 0, 1, 0}
And count of c0 = 4, c1 = 1 and c2 = 1. To make c0 = c1 = c2 = n / m = 2.
Add 1 to 6 and 2 to 12 then the array becomes {3, 2, 0, 7, 10, 14} and c0 = c1 = c2 = n / m = 2.
Approach: For each i from 0 to m – 1, find all the elements of the array that are congruent to i modulo m and store their indices in a list. Also, create a vector called extra, and let k = n / m.
We have to cycle from 0 to m – 1 twice. For each i from 0 to m – 1, if there are more elements than k in the list, remove the extra elements from this list and add them to extra. If instead there are lesser elements than k then remove the last few elements from the vector extra. For every removed index idx, increase arr[idx] by (i – arr[idx]) % m.
It is obvious that after the first m iterations, every list will have size at most k and after m more iterations all lists will have the same sizes i.e. k.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the minimum // number of operations required int minOperations( int n, int a[], int m) { int k = n / m; // To store modulos values vector<vector< int > > val(m); for ( int i = 0; i < n; ++i) { val[a[i] % m].push_back(i); } long long ans = 0; vector<pair< int , int > > extra; for ( int i = 0; i < 2 * m; ++i) { int cur = i % m; // If it's size greater than k // it needed to be decreased while ( int (val[cur].size()) > k) { int elem = val[cur].back(); val[cur].pop_back(); extra.push_back(make_pair(elem, i)); } // If it's size is less than k // it needed to be increased while ( int (val[cur].size()) < k && !extra.empty()) { int elem = extra.back().first; int mmod = extra.back().second; extra.pop_back(); val[cur].push_back(elem); ans += i - mmod; } } return ans; } // Driver code int main() { int m = 3; int a[] = { 3, 2, 0, 6, 10, 12 }; int n = sizeof (a) / sizeof (a[0]); cout << minOperations(n, a, m); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG{ static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Function to return the minimum // number of operations required static int minOperations( int n, int a[], int m) { int k = n / m; // To store modulos values @SuppressWarnings ( "unchecked" ) Vector<Integer> []val = new Vector[m]; for ( int i = 0 ; i < val.length; i++) val[i] = new Vector<Integer>(); for ( int i = 0 ; i < n; ++i) { val[a[i] % m].add(i); } long ans = 0 ; Vector<pair> extra = new Vector<>(); for ( int i = 0 ; i < 2 * m; ++i) { int cur = i % m; // If it's size greater than k // it needed to be decreased while ((val[cur].size()) > k) { int elem = val[cur].lastElement(); val[cur].removeElementAt(val[cur].size() - 1 ); extra.add( new pair(elem, i)); } // If it's size is less than k // it needed to be increased while (val[cur].size() < k && !extra.isEmpty()) { int elem = extra.get(extra.size() - 1 ).first; int mmod = extra.get(extra.size() - 1 ).second; extra.remove(extra.size() - 1 ); val[cur].add(elem); ans += i - mmod; } } return ( int )ans; } // Driver code public static void main(String[] args) { int m = 3 ; int a[] = { 3 , 2 , 0 , 6 , 10 , 12 }; int n = a.length; System.out.print(minOperations(n, a, m)); } } // This code is contributed by Princi Singh |
Python3
# Python3 implementation of the approach # Function to return the minimum # number of operations required def minOperations(n, a, m): k = n / / m # To store modulos values val = [[] for i in range (m)] for i in range ( 0 , n): val[a[i] % m].append(i) ans = 0 extra = [] for i in range ( 0 , 2 * m): cur = i % m # If it's size greater than k # it needed to be decreased while len (val[cur]) > k: elem = val[cur].pop() extra.append((elem, i)) # If it's size is less than k # it needed to be increased while ( len (val[cur]) < k and len (extra) > 0 ): elem = extra[ - 1 ][ 0 ] mmod = extra[ - 1 ][ 1 ] extra.pop() val[cur].append(elem) ans + = i - mmod return ans # Driver code if __name__ = = "__main__" : m = 3 a = [ 3 , 2 , 0 , 6 , 10 , 12 ] n = len (a) print (minOperations(n, a, m)) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the // above approach using System; using System.Collections.Generic; class GFG{ public class pair { public int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Function to return the minimum // number of operations required static int minOperations( int n, int []a, int m) { int k = n / m; // To store modulos values List< int > []val = new List< int >[m]; for ( int i = 0; i < val.Length; i++) val[i] = new List< int >(); for ( int i = 0; i < n; ++i) { val[a[i] % m].Add(i); } long ans = 0; List<pair> extra = new List<pair>(); for ( int i = 0; i < 2 * m; ++i) { int cur = i % m; // If it's size greater than k // it needed to be decreased while ((val[cur].Count) > k) { int elem = val[cur][val[cur].Count - 1]; val[cur].RemoveAt(val[cur].Count - 1); extra.Add( new pair(elem, i)); } // If it's size is less than k // it needed to be increased while (val[cur].Count < k && extra.Count != 0) { int elem = extra[extra.Count - 1].first; int mmod = extra[extra.Count - 1].second; extra.RemoveAt(extra.Count - 1); val[cur].Add(elem); ans += i - mmod; } } return ( int )ans; } // Driver code public static void Main(String[] args) { int m = 3; int []a = {3, 2, 0, 6, 10, 12}; int n = a.Length; Console.Write(minOperations(n, a, m)); } } // This code is contributed by Princi Singh |
Javascript
<script> // JavaScript implementation of the approach // Function to return the minimum // number of operations required function minOperations(n, a, m) { let k = Math.floor(n / m) // To store modulos values let val = new Array(m) for ( var i = 0; i < m; i++) val[i] = new Array() for ( var i = 0; i < n; i++) val[a[i] % m].push(i) let ans = 0 let extra = [] for ( var i = 0; i < m + m; i++) { cur = i % m // If it's size greater than k // it needed to be decreased while ((val[cur]).length > k) { let elem = val[cur].pop() extra.push([elem, i]) } // If it's size is less than k // it needed to be increased while ((val[cur]).length < k && (extra).length > 0) { let elem = extra[extra.length - 1][0] let mmod = extra[extra.length - 1][1] extra.pop() val[cur].push(elem) ans += i - mmod } } return ans } // Driver code let m = 3 let a = [3, 2, 0, 6, 10, 12] let n = a.length console.log(minOperations(n, a, m)) // This code is contributed by phasing17 </script> |
3
Contact Us