Valor mínimo por el cual se debe agregar cada elemento de Array según las condiciones dadas

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:  

1. Cree la array de frecuencias (por ejemplo , freqB[] ) de la array B[] .
2. 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 .
3. 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++ 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 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 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# 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

<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)