Minimum value by which each Array element must be added as per given conditions
Given 2 arrays A[] and B[] and an integer M. The task is to find the minimum value of X such that after changing all the elements of the array to (arr[i] + X)%M frequency of all the elements of A[] is same as the frequency of all the elements of B[]. Print “-1” if it is not possible to find any value of X.
Examples:
Input: M = 3, A[] = {0, 0, 2, 1}, B[] = {2, 0, 1, 1}
Output: 1
Explanation:
On taking x = 1 the numbers are changed to:
(0 + 1) % 3 = 1
(0 + 1) % 3 = 1
(2 + 1) % 3 = 0
(1 + 1) % 3 = 2
Hence on rearranging 1, 1, 0, 2 to 2, 0, 1, 1, array B[] is obtained.Input: M = 887, A[] = {4625, 5469, 2038, 5916}, B[] = {744, 211, 795, 695}
Output: -1
Explanation:
The conversion of A[] to B[] is not possible.
Approach: The possible value of X will be in the range [0, M] as the value after the range M will give the same result we are performing modulo to M. Below are the steps:
- Create the frequency array(say freqB[]) of the array B[].
- Now, iterate for all possible value of X in the range [0, M] and do the following:
- For each value of X in the above range update the array A[] to (arr[i] + X)%M.
- Create the frequency array(say freqA[]) of the array A[].
- If the frequency of the array freqA[] and freqB[] is the same then print this value of X.
- Else check for another value of X.
- After the above step if we don’t find the value of X then print “-1”.
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 minimum value of X int findX( int n, int m, int ar1[], int ar2[]) { // Create a frequency array for B[] int freq2[m] = { 0 }; for ( int i = 0; i < n; i++) { freq2[ar2[i]]++; } // Initialize x = -1 int x = -1; // Loop from [0 to m-1] for ( int i = 0; i < m; i++) { int cnt = 0; int freq1[m] = { 0 }; // Create a frequency array // for fixed x for all ar[i] for ( int j = 0; j < n; j++) { freq1[(ar1[j] + i) % m]++; } bool flag = true ; // Comparing freq1[] and freq2[] for ( int k = 0; k < m; k++) { if (freq1[k] != freq2[k]) { flag = false ; break ; } } // If condition is satisfied // then break out from loop if (flag) { x = i; break ; } } // Return the answer return x; } // Driver Code int main() { // Given value of M int M = 3; // Given arrays ar1[] and ar2[] int ar1[] = { 0, 0, 2, 1 }; int ar2[] = { 2, 0, 1, 1 }; int N = sizeof arr1 / sizeof arr1[0]; cout << findX(N, M, ar1, ar2) << '\n' ; return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find minimum value of X static int findX( int n, int m, int ar1[], int ar2[]) { // Create a frequency array for B[] int freq2[] = new int [m]; for ( int i = 0 ; i < m; i++) freq2[i] = 0 ; for ( int i = 0 ; i < n; i++) { freq2[ar2[i]]++; } // Initialize x = -1 int x = - 1 ; // Loop from [0 to m-1] for ( int i = 0 ; i < m; i++) { int cnt = 0 ; int freq1[] = new int [m]; for ( int j = 0 ; j < m; j++) { freq1[j] = 0 ; } // Create a frequency array // for fixed x for all ar[i] for ( int j = 0 ; j < n; j++) { freq1[(ar1[j] + i) % m]++; } boolean flag = true ; // Comparing freq1[] and freq2[] for ( int k = 0 ; k < m; k++) { if (freq1[k] != freq2[k]) { flag = false ; break ; } } // If condition is satisfied // then break out from loop if (flag) { x = i; break ; } } // Return the answer return x; } // Driver Code public static void main(String[] args) { // Given value of M int M = 3 ; // Given arrays ar1[] and ar2[] int ar1[] = { 0 , 0 , 2 , 1 }; int ar2[] = { 2 , 0 , 1 , 1 }; int N = ar1.length; System.out.println(findX(N, M, ar1, ar2)); } } // This code is contributed by Stream_Cipher |
Python3
# Python3 program for # the above approach # Function to find # minimum value of X def findX(n, m, ar1, ar2): # Create a frequency # array for B[] freq2 = [ 0 ] * m for i in range (n): freq2[ar2[i]] + = 1 # Initialize x = -1 x = - 1 # Loop from [0 to m - 1] for i in range (m): cnt = 0 freq1 = [ 0 ] * m # Create a frequency array # for fixed x for all ar[i] for j in range (n): freq1[(ar1[j] + i) % m] + = 1 flag = True # Comparing freq1[] # and freq2[] for k in range (m): if (freq1[k] ! = freq2[k]): flag = False break # If condition is satisfied # then break out from loop if (flag): x = i break # Return the answer return x # Driver Code if __name__ = = "__main__" : # Given value of M M = 3 # Given arrays ar1[] # and ar2[] ar1 = [ 0 , 0 , 2 , 1 ] ar2 = [ 2 , 0 , 1 , 1 ] N = len (ar1) print (findX(N, M, ar1, ar2)) # This code is contributed by Chitranayal |
C#
// C# program for the above approach using System; class GFG { // Function to find minimum value of X static int findX( int n, int m, int []ar1 , int []ar2) { // Create a frequency array for B[] int []freq2 = new int [m]; for ( int i = 0; i < m; i++) freq2[i] = 0; for ( int i = 0; i < n; i++) { freq2[ar2[i]]++; } // Initialize x = -1 int x = -1; // Loop from [0 to m-1] for ( int i = 0; i < m; i++) { int cnt = 0; int []freq1 = new int [m]; for ( int j = 0; j < m; j++) { freq1[j] = 0; } // Create a frequency array // for fixed x for all ar[i] for ( int j = 0; j < n; j++) { freq1[(ar1[j] + i) % m]++; } Boolean flag = true ; // Comparing freq1[] and freq2[] for ( int k = 0; k < m; k++) { if (freq1[k] != freq2[k]) { flag = false ; break ; } } // If condition is satisfied // then break out from loop if (flag) { x = i; break ; } } // Return the answer return x; } // Driver Code public static void Main(String[] args) { // Given value of M int M = 3; // Given arrays ar1[] and ar2[] int []ar1 = { 0, 0, 2, 1 }; int []ar2 = { 2, 0, 1, 1 }; int N = ar1.Length; Console.Write(findX(N, M, ar1, ar2)); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript program for the above approach // Function to find minimum value of X function findX(n, m, ar1, ar2) { // Create a frequency array for B[] let freq2 = new Array(m); for (let i = 0; i < m; i++) freq2[i] = 0; for (let i = 0; i < n; i++) { freq2[ar2[i]]++; } // Initialize x = -1 let x = -1; // Loop from [0 to m-1] for (let i = 0; i < m; i++) { let cnt = 0; let freq1 = new Array(m); for (let i = 0; i < m; i++) freq1[i] = 0; // Create a frequency array // for fixed x for all ar[i] for (let j = 0; j < n; j++) { freq1[(ar1[j] + i) % m]++; } let flag = true ; // Comparing freq1[] and freq2[] for (let k = 0; k < m; k++) { if (freq1[k] != freq2[k]) { flag = false ; break ; } } // If condition is satisfied // then break out from loop if (flag) { x = i; break ; } } // Return the answer return x; } // Driver Code // Given value of M let M = 3; // Given arrays ar1[] and ar2[] let ar1 = [ 0, 0, 2, 1 ]; let ar2 = [ 2, 0, 1, 1 ]; let N = ar1.length; document.write(findX(N, M, ar1, ar2) + "<br>" ); // This code is contributed by Surbhi Tyagi. </script> |
1
Time Complexity: O(N*M), where N is the number of elements in the array and M is an integer.
Auxiliary Space: O(N)
Contact Us