Dadas dos arrays A[] y B[] de igual tamaño N , la tarea es verificar si A[] puede hacerse igual a B[] invirtiendo cualquier subarreglo de A solo una vez.
Ejemplos:
Entrada: A[] = {1, 3, 2, 4}
B[] = {1, 2, 3, 4}
Salida: Sí
Explicación:
El subarreglo {3, 2} se puede invertir en {2, 3 }, lo que hace que A sea igual a B.
Entrada: A[] = {1, 4, 2, 3}
B[] = {1, 2, 3, 4}
Salida: No
Explicación:
No hay ningún subarreglo de A que, cuando se invierte, haga que A sea igual a B.
Enfoque ingenuo: compruebe todos los subconjuntos de A[] y compare los dos conjuntos después de invertir el subconjunto.
Complejidad temporal: O(N 2 ).
Enfoque eficiente:
- Primero, encuentre el índice inicial y final del subarreglo que no es igual en A y B .
- Luego, al invertir el subarreglo requerido, podemos verificar si A puede hacerse igual a B o no.
- El índice inicial es el primer índice en los arreglos para los cuales A[i] != B[i] y el índice final es el último índice en los arreglos para los cuales A[i] != B[i] .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation to
// check whether two arrays
// can be made equal by
// reversing a sub-array
// only once
#include <bits/stdc++.h>
using namespace std;
// Function to check whether two arrays
// can be made equal by reversing
// a sub-array only once
void checkArray(int A[], int B[], int N)
{
// Integer variable for
// storing the required
// starting and ending
// indices in the array
int start = 0;
int end = N - 1;
// Finding the smallest index
// for which A[i] != B[i]
// i.e the starting index
// of the unequal sub-array
for (int i = 0; i < N; i++) {
if (A[i] != B[i]) {
start = i;
break;
}
}
// Finding the largest index
// for which A[i] != B[i]
// i.e the ending index
// of the unequal sub-array
for (int i = N - 1; i >= 0; i--) {
if (A[i] != B[i]) {
end = i;
break;
}
}
// Reversing the sub-array
// A[start], A[start+1] .. A[end]
reverse(A + start, A + end + 1);
// Checking whether on reversing
// the sub-array A[start]...A[end]
// makes the arrays equal
for (int i = 0; i < N; i++) {
if (A[i] != B[i]) {
// If any element of the
// two arrays is unequal
// print No and return
cout << "No" << endl;
return;
}
}
// Print Yes if arrays are
// equal after reversing
// the sub-array
cout << "Yes" << endl;
}
// Driver code
int main()
{
int A[] = { 1, 3, 2, 4 };
int B[] = { 1, 2, 3, 4 };
int N = sizeof(A) / sizeof(A[0]);
checkArray(A, B, N);
return 0;
}
Java
// Java implementation to
// check whether two arrays
// can be made equal by
// reversing a sub-array
// only once
import java.util.*;
class GFG{
// Function to check whether two arrays
// can be made equal by reversing
// a sub-array only once
static void checkArray(int A[], int B[], int N)
{
// Integer variable for
// storing the required
// starting and ending
// indices in the array
int start = 0;
int end = N - 1;
// Finding the smallest index
// for which A[i] != B[i]
// i.e the starting index
// of the unequal sub-array
for (int i = 0; i < N; i++)
{
if (A[i] != B[i])
{
start = i;
break;
}
}
// Finding the largest index
// for which A[i] != B[i]
// i.e the ending index
// of the unequal sub-array
for (int i = N - 1; i >= 0; i--)
{
if (A[i] != B[i])
{
end = i;
break;
}
}
// Reversing the sub-array
// A[start], A[start+1] .. A[end]
Collections.reverse(Arrays.asList(A));
// Checking whether on reversing
// the sub-array A[start]...A[end]
// makes the arrays equal
for (int i = 0; i < N; i++)
{
if (A[i] != B[i])
{
// If any element of the
// two arrays is unequal
// print No and return
System.out.println("No");
return;
}
}
// Print Yes if arrays are
// equal after reversing
// the sub-array
System.out.println("Yes");
}
// Driver code
public static void main(String[] args)
{
int A[] = { 1, 3, 2, 4 };
int B[] = { 1, 2, 3, 4 };
int N = A.length;
checkArray(A, B, N);
}
}
// This Code is contributed by rock_cool
Python3
# Python3 implementation to
# check whether two arrays
# can be made equal by
# reversing a sub-array
# only once
# Function to check whether two arrays
# can be made equal by reversing
# a sub-array only once
def checkArray(A, B, N):
# Integer variable for
# storing the required
# starting and ending
# indices in the array
start = 0
end = N - 1
# Finding the smallest index
# for which A[i] != B[i]
# i.e the starting index
# of the unequal sub-array
for i in range(N):
if (A[i] != B[i]):
start = i
break
# Finding the largest index
# for which A[i] != B[i]
# i.e the ending index
# of the unequal sub-array
for i in range(N - 1, -1, -1):
if (A[i] != B[i]):
end = i
break
# Reversing the sub-array
# A[start], A[start+1] .. A[end]
A[start:end + 1] = reversed(A[start:end + 1])
# Checking whether on reversing
# the sub-array A[start]...A[end]
# makes the arrays equal
for i in range(N):
if (A[i] != B[i]):
# If any element of the
# two arrays is unequal
# print No and return
print("No")
return
# Print Yes if arrays are
# equal after reversing
# the sub-array
print("Yes")
# Driver code
if __name__ == '__main__':
A = [ 1, 3, 2, 4 ]
B = [ 1, 2, 3, 4 ]
N = len(A)
checkArray(A, B, N)
# This code is contributed by mohit kumar 29
C#
// C# implementation to
// check whether two arrays
// can be made equal by
// reversing a sub-array
// only once
using System;
class GFG{
// Function to check whether two arrays
// can be made equal by reversing
// a sub-array only once
static void checkArray(int []A, int []B, int N)
{
// Integer variable for
// storing the required
// starting and ending
// indices in the array
int start = 0;
int end = N - 1;
// Finding the smallest index
// for which A[i] != B[i]
// i.e the starting index
// of the unequal sub-array
for(int i = 0; i < N; i++)
{
if (A[i] != B[i])
{
start = i;
break;
}
}
// Finding the largest index
// for which A[i] != B[i]
// i.e the ending index
// of the unequal sub-array
for(int i = N - 1; i >= 0; i--)
{
if (A[i] != B[i])
{
end = i;
break;
}
}
// Reversing the sub-array
// A[start], A[start+1] .. A[end]
Array.Reverse(A, start, end);
// Checking whether on reversing
// the sub-array A[start]...A[end]
// makes the arrays equal
for(int i = 0; i < N; i++)
{
if (A[i] != B[i])
{
// If any element of the
// two arrays is unequal
// print No and return
Console.Write("No");
return;
}
}
// Print Yes if arrays are
// equal after reversing
// the sub-array
Console.Write("Yes");
}
// Driver code
public static void Main(string[] args)
{
int []A = { 1, 3, 2, 4 };
int []B = { 1, 2, 3, 4 };
int N = A.Length;
checkArray(A, B, N);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript implementation to
// check whether two arrays
// can be made equal by
// reversing a sub-array
// only once
// Function to check whether two arrays
// can be made equal by reversing
// a sub-array only once
function checkArray(A, B, N)
{
// Integer variable for
// storing the required
// starting and ending
// indices in the array
var start = 0;
var end = N - 1;
// Finding the smallest index
// for which A[i] != B[i]
// i.e the starting index
// of the unequal sub-array
for (var i = 0; i < N; i++) {
if (A[i] != B[i]) {
start = i;
break;
}
}
// Finding the largest index
// for which A[i] != B[i]
// i.e the ending index
// of the unequal sub-array
for (var i = N - 1; i >= 0; i--) {
if (A[i] != B[i]) {
end = i;
break;
}
}
// Reversing the sub-array
// A[start], A[start+1] .. A[end]
var l = start;
var r = end;
var d = parseInt((r-l+2)/2);
for(var i=0;i<d;i++)
{
var t = A[l+i];
A[l+i] = A[r-i];
A[r-i] = t;
}
// Checking whether on reversing
// the sub-array A[start]...A[end]
// makes the arrays equal
for (var i = 0; i < N; i++) {
if (A[i] != B[i]) {
// If any element of the
// two arrays is unequal
// print No and return
document.write( "No" );
return;
}
}
// Print Yes if arrays are
// equal after reversing
// the sub-array
document.write( "Yes" );
}
// Driver code
var A = [1, 3, 2, 4];
var B = [1, 2, 3, 4];
var N = A.length;
checkArray(A, B, N);
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar : O(1)