Smallest number to be added in first Array modulo M to make frequencies of both Arrays equal
Given two arrays A[] and B[] consisting of N positive integers and an integer M, the task is to find the minimum value of X such that operation (A[i] + X) % M performed on every element of array A[] results in the formation of an array with frequency of elements same as that in another given array B[].
Examples:
Input: N = 4, M = 3, A[] = {0, 0, 2, 1}, B[] = {2, 0, 1, 1}
Output: 1
Explanation:
Modifying the given array A[] to { (0+1)%3, (0+1)%3, (2+1)%3, (1+1)%3 }
= { 1%3, 1%3, 3%3, 2%3 },
= { 1, 1, 0, 2 }, which is equivalent to B[] in terms of frequency of distinct elements.Input: N = 5, M = 10, A[] = {0, 0, 0, 1, 2}, B[] = {2, 1, 0, 0, 0}
Output: 0
Explanation:
Frequency of elements in both the arrays are already equal.
Approach: This problem can be solved by using Greedy Approach. Follow the steps below:
- There will be at least one possible value of X such that for every index i, ( A[i] + X ) % M = B[0].
- Find all the possible values of X that convert each element of A[] to the first element of B[].
- Check whether these possible X values satisfy the other remaining values of B[].
- If there are multiple answers, take the minimum value of X.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Utility function to find // the answer int moduloEquality( int A[], int B[], int n, int m) { // Stores the frequencies of // array elements map< int , int > mapA, mapB; for ( int i = 0; i < n; i++) { mapA[A[i]]++; mapB[B[i]]++; } // Stores the possible values // of X set< int > possibleValues; int FirstElement = B[0]; for ( int i = 0; i < n; i++) { int cur = A[i]; // Generate possible positive // values of X possibleValues .insert( cur > FirstElement ? m - cur + FirstElement : FirstElement - cur); } // Initialize answer // to MAX value int ans = INT_MAX; for ( auto it : possibleValues) { // Flag to check if the // current element of the // set can be considered bool possible = true ; for ( auto it2 : mapA) { // If the frequency of an element // in A[] is not equal to that // in B[] after the operation if (it2.second != mapB[(it2.first + it) % m]) { // Current set element // cannot be considered possible = false ; break ; } } // Update minimum value of X if (possible) { ans = min(ans, it); } } return ans; } // Driver Code int main() { int n = 4; int m = 3; int A[] = { 0, 0, 2, 1 }; int B[] = { 2, 0, 1, 1 }; cout << moduloEquality(A, B, n, m) << endl; return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Utility function to find // the answer static int moduloEquality( int A[], int B[], int n, int m) { // Stores the frequencies of // array elements HashMap<Integer, Integer> mapA = new HashMap<Integer, Integer>(); HashMap<Integer, Integer> mapB = new HashMap<Integer, Integer>(); for ( int i = 0 ; i < n; i++) { if (mapA.containsKey(A[i])) { mapA.put(A[i], mapA.get(A[i]) + 1 ); } else { mapA.put(A[i], 1 ); } if (mapB.containsKey(B[i])) { mapB.put(B[i], mapB.get(B[i]) + 1 ); } else { mapB.put(B[i], 1 ); } } // Stores the possible values // of X HashSet<Integer> possibleValues = new HashSet<Integer>(); int FirstElement = B[ 0 ]; for ( int i = 0 ; i < n; i++) { int cur = A[i]; // Generate possible positive // values of X possibleValues.add(cur > FirstElement ? m - cur + FirstElement : FirstElement - cur); } // Initialize answer // to MAX value int ans = Integer.MAX_VALUE; for ( int it : possibleValues) { // Flag to check if the // current element of the // set can be considered boolean possible = true ; for (Map.Entry<Integer, Integer> it2 : mapA.entrySet()) { // If the frequency of an element // in A[] is not equal to that // in B[] after the operation if (it2.getValue() != mapB.get((it2.getKey() + it) % m)) { // Current set element // cannot be considered possible = false ; break ; } } // Update minimum value of X if (possible) { ans = Math.min(ans, it); } } return ans; } // Driver Code public static void main(String[] args) { int n = 4 ; int m = 3 ; int A[] = { 0 , 0 , 2 , 1 }; int B[] = { 2 , 0 , 1 , 1 }; System.out.print(moduloEquality(A, B, n, m) + "\n" ); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach import sys from collections import defaultdict # Utility function to find # the answer def moduloEquality(A, B, n, m): # Stores the frequencies of # array elements mapA = defaultdict( int ) mapB = defaultdict( int ) for i in range (n): mapA[A[i]] + = 1 mapB[B[i]] + = 1 # Stores the possible values # of X possibleValues = set () FirstElement = B[ 0 ] for i in range (n): cur = A[i] # Generate possible positive # values of X if cur > FirstElement: possibleValues.add(m - cur + FirstElement) else : possibleValues.add(FirstElement - cur) # Initialize answer # to MAX value ans = sys.maxsize for it in possibleValues: # Flag to check if the # current element of the # set can be considered possible = True for it2 in mapA: # If the frequency of an element # in A[] is not equal to that # in B[] after the operation if (mapA[it2] ! = mapB[(it2 + it) % m]): # Current set element # cannot be considered possible = False break # Update minimum value of X if (possible): ans = min (ans, it) return ans # Driver Code if __name__ = = "__main__" : n = 4 m = 3 A = [ 0 , 0 , 2 , 1 ] B = [ 2 , 0 , 1 , 1 ] print (moduloEquality(A, B, n, m)) # This code is contributed by chitranayal |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Utility function to find // the answer static int moduloEquality( int [] A, int [] B, int n, int m) { // Stores the frequencies of // array elements Dictionary< int , int > mapA = new Dictionary< int , int >(); Dictionary< int , int > mapB = new Dictionary< int , int >(); for ( int i = 0; i < n; i++) { if (mapA.ContainsKey(A[i])) { mapA[A[i]] = mapA[A[i]] + 1; } else { mapA.Add(A[i], 1); } if (mapB.ContainsKey(B[i])) { mapB[B[i]] = mapB[B[i]] + 1; } else { mapB.Add(B[i], 1); } } // Stores the possible values // of X HashSet< int > possibleValues = new HashSet< int >(); int FirstElement = B[0]; for ( int i = 0; i < n; i++) { int cur = A[i]; // Generate possible positive // values of X possibleValues.Add(cur > FirstElement ? m - cur + FirstElement : FirstElement - cur); } // Initialize answer // to MAX value int ans = Int32.MaxValue; foreach ( int it in possibleValues) { // Flag to check if the // current element of the // set can be considered bool possible = true ; foreach (KeyValuePair< int , int > it2 in mapA) { // If the frequency of an element // in A[] is not equal to that // in B[] after the operation if (it2.Value != mapB[(it2.Key + it) % m]) { // Current set element // cannot be considered possible = false ; break ; } } // Update minimum value of X if (possible) { ans = Math.Min(ans, it); } } return ans; } // Driver code static void Main() { int n = 4; int m = 3; int [] A = { 0, 0, 2, 1 }; int [] B = { 2, 0, 1, 1 }; Console.WriteLine(moduloEquality(A, B, n, m)); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // JavaScript program for the above approach // Utility function to find // the answer function moduloEquality(A, B, n, m) { // Stores the frequencies of // array elements var mapA = new Map(), mapB = new Map(); for ( var i = 0; i < n; i++) { if (mapA.has(A[i])) mapA.set(A[i], mapA.get(A[i])+1) else mapA.set(A[i], 1) if (mapB.has(B[i])) mapB.set(B[i], mapB.get(B[i])+1) else mapB.set(B[i], 1) } // Stores the possible values // of X var possibleValues = new Set(); var FirstElement = B[0]; for ( var i = 0; i < n; i++) { var cur = A[i]; // Generate possible positive // values of X possibleValues .add( cur > FirstElement ? m - cur + FirstElement : FirstElement - cur); } // Initialize answer // to MAX value var ans = 1000000000; possibleValues.forEach(it => { // Flag to check if the // current element of the // set can be considered var possible = true ; mapA.forEach((value, key) => { // If the frequency of an element // in A[] is not equal to that // in B[] after the operation if (value != mapB.get((key + it) % m)) { // Current set element // cannot be considered possible = false ; } }); // Update minimum value of X if (possible) { ans = Math.min(ans, it); } }); return ans; } // Driver Code var n = 4; var m = 3; var A = [0, 0, 2, 1]; var B = [2, 0, 1, 1]; document.write( moduloEquality(A, B, n, m)); </script> |
1
Time Complexity: O(N2)
Auxiliary Space: O(N)