Dadas 2 arrays A[] y B[] y un entero M . La tarea es encontrar el valor mínimo de X tal que después de cambiar todos los elementos de la array a (arr[i] + X)%M la frecuencia de todos los elementos de A[] es la misma que la frecuencia de todos los elementos de B[] . Imprime “-1” si no es posible encontrar ningún valor de X.
Ejemplos:
Entrada: M = 3, A[] = {0, 0, 2, 1}, B[] = {2, 0, 1, 1}
Salida: 1
Explicación:
Al tomar x = 1 los números se cambian a:
( 0 + 1) % 3 = 1
(0 + 1) % 3 = 1
(2 + 1) % 3 = 0
(1 + 1) % 3 = 2
Por lo tanto, al reorganizar 1, 1, 0, 2 a 2, 0, 1, 1, se obtiene la array B[].Entrada: M = 887, A[] = {4625, 5469, 2038, 5916}, B[] = {744, 211, 795, 695}
Salida: -1
Explicación:
La conversión de A[] a B[] es imposible.
Enfoque: El posible valor de X estará en el rango [0, M] ya que el valor después del rango M dará el mismo resultado que estamos realizando módulo a M. A continuación se muestran los pasos:
- Cree la array de frecuencias (por ejemplo , freqB[] ) de la array B[] .
- Ahora, itere para todos los valores posibles de X en el rango [0, M] y haga lo siguiente:
- Para cada valor de X en el rango anterior, actualice la array A[] a (arr[i] + X)%M .
- Cree la array de frecuencias (digamos freqA[] ) de la array A[] .
- Si la frecuencia de la array freqA[] y freqB[] es la misma, imprima este valor de X.
- De lo contrario, busque otro valor de X .
- Después del paso anterior, si no encontramos el valor de X , imprima «-1» .
A continuación se muestra la implementación del enfoque anterior:
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
Complejidad de tiempo: O(N*M), donde N es el número de elementos de la array y M es un número entero.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por mayank17bcs1149 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA