Minimice el número de rotaciones en la array A de modo que sea igual a B

Dadas las arrays , A[] y la array B[] de tamaño N , la tarea es minimizar el número de rotaciones (izquierda o derecha) en A de modo que sea igual a B .

Nota: Siempre es posible cambiar A por B.

Ejemplos:

Entrada: A[] = {1, 2, 3, 4, 5},  
B[] = {4, 5, 1, 2, 3} 
Salida: 2
Explicación: A[] se puede cambiar a B[]:
Activado izquierda girando A[] 3 o, 
a la derecha girando A[] 2 veces.
Por lo tanto, el número mínimo de rotaciones requeridas son 2.

Entrada: A[] = {13, 12, 7, 18, 4, 5, 1},  
B[] = {12, 7, 18, 4, 5, 1, 13}
Salida: 1
Explicación: A[] puede cambiarse a B[]: a
la izquierda girando A[] 1 vez o, 
a la derecha girando A[] 6 veces.
Por lo tanto, el número mínimo de rotaciones requeridas es 1.

Enfoque: La solución se basa simplemente en seguir rotando el arreglo A[] y verificarlo. Siga los pasos que se mencionan a continuación:

• Gire a la izquierda la array A[] hasta que sea igual a B[] y cuente el número de rotaciones requeridas.
• Del mismo modo , gire a la derecha la array A[] hasta que sea igual a B[] y cuente el número de rotaciones.
• El mínimo de ambas rotaciones será la respuesta .

A continuación se muestra la implementación del método anterior:

// C++ code to minimize number of rotations
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if two arrays are equal
bool check(int A[], int B[], int N)
{
    bool flag = true;
    for (int i = 0; i < N; i++) {
        if (A[i] != B[i]) {
            flag = false;
            break;
        }
    }
    return flag;
}
 
// Function to left rotate an array
void Leftrotate(int A[], int N)
{
    int temp = A[0];
    for (int i = 0; i < N - 1; i++) {
        A[i] = A[i + 1];
    }
    A[N - 1] = temp;
}
 
// Function to right rotate an array
void Rightrotate(int A[], int N)
{
    int temp = A[N - 1];
    for (int i = N - 1; i > 0; i--) {
        A[i] = A[i - 1];
    }
    A[0] = temp;
}
 
// Function to minimize number of rotations
int minRotations(int A[], int B[], int N)
{
    int C[N];
    for (int i = 0; i < N; i++)
        C[i] = A[i];
    int a = 0, b = 0;
 
    // Right rotate the array
    // till it is equal to B
    while (check(A, B, N) == false) {
        Rightrotate(A, N);
        a++;
    }
 
    // Left rotate the array
    // till it is equal to B
    while (check(C, B, N) == false) {
        Leftrotate(C, N);
        b++;
    }
 
    int ans = min(a, b);
    return ans;
}
 
// Driver code
int main()
{
    int A[] = { 13, 12, 7, 18, 4, 5, 1 };
    int B[] = { 12, 7, 18, 4, 5, 1, 13 };
    int N = sizeof(A) / sizeof(A[0]);
 
    int ans = minRotations(A, B, N);
    cout << ans;
 
    return 0;
}

// C code to minimize number of rotations
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
 
// Function to check if two arrays are equal
bool check(int A[], int B[], int N)
{
    bool flag = true;
    for (int i = 0; i < N; i++) {
        if (A[i] != B[i]) {
            flag = false;
            break;
        }
    }
    return flag;
}
 
// Function to left rotate an array
void Leftrotate(int A[], int N)
{
    int temp = A[0];
    for (int i = 0; i < N - 1; i++) {
        A[i] = A[i + 1];
    }
    A[N - 1] = temp;
}
 
// Function to right rotate an array
void Rightrotate(int A[], int N)
{
    int temp = A[N - 1];
    for (int i = N - 1; i > 0; i--) {
        A[i] = A[i - 1];
    }
    A[0] = temp;
}
 
// Function to minimize number of rotations
int minRotations(int A[], int B[], int N)
{
    int ans, a = 0, b = 0;
    int C[N];
    for (int i = 0; i < N; i++)
        C[i] = A[i];
 
    // Right rotate the array
    // till it is equal to B
    while (check(A, B, N) == false) {
        Rightrotate(A, N);
        a++;
    }
 
    // Left rotate the array
    // till it is equal to B
    while (check(C, B, N) == false) {
        Leftrotate(C, N);
        b++;
    }
    ans = a <= b ? a : b;
    return ans;
}
 
// Driver code
int main()
{
    int A[] = { 13, 12, 7, 18, 4, 5, 1 };
    int B[] = { 12, 7, 18, 4, 5, 1, 13 };
    int N = sizeof(A) / sizeof(A[0]);
 
    int ans = minRotations(A, B, N);
    printf("%d", ans);
 
    return 0;
}

// Java code to minimize number of rotations
import java.util.*;
public class GFG
{
   
// Function to check if two arrays are equal
static boolean check(int A[], int B[], int N)
{
    boolean flag = true;
    for (int i = 0; i < N; i++) {
        if (A[i] != B[i]) {
            flag = false;
            break;
        }
    }
    return flag;
}
 
// Function to left rotate an array
static void Leftrotate(int A[], int N)
{
    int temp = A[0];
    for (int i = 0; i < N - 1; i++) {
        A[i] = A[i + 1];
    }
    A[N - 1] = temp;
}
 
// Function to right rotate an array
static void Rightrotate(int A[], int N)
{
    int temp = A[N - 1];
    for (int i = N - 1; i > 0; i--) {
        A[i] = A[i - 1];
    }
    A[0] = temp;
}
 
// Function to minimize number of rotations
static int minRotations(int A[], int B[], int N)
{
    int C[] = new int[N];
    for (int i = 0; i < N; i++)
        C[i] = A[i];
    int a = 0, b = 0;
 
    // Right rotate the array
    // till it is equal to B
    while (check(A, B, N) == false) {
        Rightrotate(A, N);
        a++;
    }
 
    // Left rotate the array
    // till it is equal to B
    while (check(C, B, N) == false) {
        Leftrotate(C, N);
        b++;
    }
 
    int ans = Math.min(a, b);
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    int A[] = { 13, 12, 7, 18, 4, 5, 1 };
    int B[] = { 12, 7, 18, 4, 5, 1, 13 };
    int N = A.length;
 
    int ans = minRotations(A, B, N);
    System.out.println(ans);
 
}
}
 
// This code is contributed by Samim Hossain Mondal.

# Python code for the above approach
 
# Function to check if two arrays are equal
def check(A, B, N):
    flag = True;
    for i in range(N):
        if (A[i] != B[i]):
            flag = False;
            break;
    return flag;
 
# Function to left rotate an array
def Leftrotate(A, N):
    temp = A[0];
    for i in range(N - 1):
        A[i] = A[i + 1];
    A[N - 1] = temp;
 
# Function to right rotate an array
def Rightrotate(A, N):
    temp = A[N - 1];
    for i in range(N - 1, 0, -1):
        A[i] = A[i - 1];
    A[0] = temp;
 
# Function to minimize number of rotations
def minRotations(A, B, N):
    C = [0] * N
    for i in range(N):
        C[i] = A[i];
    a = 0
    b = 0
 
    # Right rotate the array
    # till it is equal to B
    while (check(A, B, N) == False):
        Rightrotate(A, N);
        a += 1
 
    # Left rotate the array
    # till it is equal to B
    while (check(C, B, N) == False):
        Leftrotate(C, N);
        b += 1
 
    ans = min(a, b);
    return ans;
 
# Driver code
A = [13, 12, 7, 18, 4, 5, 1];
B = [12, 7, 18, 4, 5, 1, 13];
N = len(A)
 
ans = minRotations(A, B, N);
print(ans);
 
# This code is contributed by gfgking

// C# code to minimize number of rotations
using System;
public class GFG
{
 
  // Function to check if two arrays are equal
  static bool check(int[] A, int[] B, int N)
  {
    bool flag = true;
    for (int i = 0; i < N; i++)
    {
      if (A[i] != B[i])
      {
        flag = false;
        break;
      }
    }
    return flag;
  }
 
  // Function to left rotate an array
  static void Leftrotate(int[] A, int N)
  {
    int temp = A[0];
    for (int i = 0; i < N - 1; i++)
    {
      A[i] = A[i + 1];
    }
    A[N - 1] = temp;
  }
 
  // Function to right rotate an array
  static void Rightrotate(int[] A, int N)
  {
    int temp = A[N - 1];
    for (int i = N - 1; i > 0; i--)
    {
      A[i] = A[i - 1];
    }
    A[0] = temp;
  }
 
  // Function to minimize number of rotations
  static int minRotations(int[] A, int[] B, int N)
  {
    int[] C = new int[N];
    for (int i = 0; i < N; i++)
      C[i] = A[i];
    int a = 0, b = 0;
 
    // Right rotate the array
    // till it is equal to B
    while (check(A, B, N) == false)
    {
      Rightrotate(A, N);
      a++;
    }
 
    // Left rotate the array
    // till it is equal to B
    while (check(C, B, N) == false)
    {
      Leftrotate(C, N);
      b++;
    }
 
    int ans = Math.Min(a, b);
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int[] A = { 13, 12, 7, 18, 4, 5, 1 };
    int[] B = { 12, 7, 18, 4, 5, 1, 13 };
    int N = A.Length;
 
    int ans = minRotations(A, B, N);
    Console.Write(ans);
 
  }
}
 
// This code is contributed by Saurabh Jaiswal

<script>
      // JavaScript code for the above approach
 
      // Function to check if two arrays are equal
      function check(A, B, N) {
          let flag = true;
          for (let i = 0; i < N; i++) {
              if (A[i] != B[i]) {
                  flag = false;
                  break;
              }
          }
          return flag;
      }
 
      // Function to left rotate an array
      function Leftrotate(A, N) {
          let temp = A[0];
          for (let i = 0; i < N - 1; i++) {
              A[i] = A[i + 1];
          }
          A[N - 1] = temp;
      }
 
      // Function to right rotate an array
      function Rightrotate(A, N) {
          let temp = A[N - 1];
          for (let i = N - 1; i > 0; i--) {
              A[i] = A[i - 1];
          }
          A[0] = temp;
      }
 
      // Function to minimize number of rotations
      function minRotations(A, B, N) {
          let C = new Array(N);
          for (let i = 0; i < N; i++)
              C[i] = A[i];
          let a = 0, b = 0;
 
          // Right rotate the array
          // till it is equal to B
          while (check(A, B, N) == false) {
              Rightrotate(A, N);
              a++;
          }
 
          // Left rotate the array
          // till it is equal to B
          while (check(C, B, N) == false) {
              Leftrotate(C, N);
              b++;
          }
 
          let ans = Math.min(a, b);
          return ans;
      }
 
      // Driver code
      let A = [13, 12, 7, 18, 4, 5, 1];
      let B = [12, 7, 18, 4, 5, 1, 13];
      let N = A.length;
 
      let ans = minRotations(A, B, N);
      document.write(ans);
 
// This code is contributed by Potta Lokesh
  </script>

1

Complejidad Temporal: O(N ² )
Espacio Auxiliar: O(N), ya que se ha añadido N espacio extra.