Dadas dos arrays arr1[] y arr2[] de N enteros. Podemos elegir dos elementos adyacentes de la array arr1[] e intercambiarlos si son de paridad opuesta, la tarea es verificar si es posible convertir la array arr1[] en la array arr2[] realizando la operación dada en arr1[ ] . Imprima «Sí» si es posible convertir la array arr1[] en arr2[] De lo contrario, imprima «No» .
Ejemplos:
Entrada: arr1[] = {5, 7, 8, 2, 10, 13}, arr2[] = {8, 5, 2, 7, 13, 10}
Salida: Sí
Explicación:
Al principio, intercambie 10 y 13 para que arr1[] = [5, 7, 8, 2, 13, 10].
Ahora, intercambie 7 y 8 para que arr1[] = [5, 8, 7, 2, 13, 10].
Ahora, intercambie 5 y 8 para que arr1[] = [8, 5, 7, 2, 13, 10].
Ahora, intercambie 7 y 2 para que arr1[] = [8, 5, 2, 7, 13, 10] = arr2[].
En cada operación, intercambiamos elementos adyacentes con diferente paridad.
Entrada: arr1[] = {0, 1, 13, 3, 4, 14, 6}, arr2[] = {0, 1, 14, 3, 4, 13, 6}
Salida: No
Explicación:
No es posible para intercambiar 13, 14 porque no son adyacentes.
Enfoque: el problema se puede resolver utilizando el enfoque codicioso . Ya que no podemos intercambiar dos números pares o impares. Entonces, la posición relativa de los números pares e impares en las arrays arr1[] y arr2[] debe ser exactamente la misma para que ambas arrays sean iguales a la operación dada. A continuación se muestran los pasos:
- Cree dos arrays (por ejemplo , par[] e impar[] ) inserte todos los números pares e impares de arr1[] en par[] e impar[] respectivamente.
- Ahora compruebe si los números pares e impares en arr2[] están en el mismo orden que en even[] y odd[] .
- Si los pasos anteriores no dan ningún número de arr2[] que no esté en el orden de los números en arreglos pares [] e impares[] respectivamente, entonces, imprima “Sí”; de lo contrario, imprima “No” .
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 which checks if it is
// possible to convert arr1[] to
// arr2[] by given operations
void convert(int a[], int b[], int n)
{
// even[] will store the even
// elements of a[]
// odd[] will store the odd
// elements of a[]
vector<int> even, odd;
// Traverse a[] and insert the even
// and odd element respectively
for (int x = 0; x < n; x++) {
if (a[x] % 2 == 0)
even.push_back(a[x]);
else
odd.push_back(a[x]);
}
// ei points to the next
// available even element
// oi points to the next
// available odd element
int ei = 0, oi = 0;
// poss will store whether the
// given transformation
// of a[] to b[] is possible
bool poss = true;
// Traverse b[]
for (int x = 0; x < n; x++) {
if (b[x] % 2 == 0) {
// Check if both even
// elements are equal
if (ei < even.size()
&& b[x] == even[ei]) {
ei++;
}
else {
poss = false;
break;
}
}
else {
// Check if both odd
// elements are equal
if (oi < odd.size()
&& b[x] == odd[oi]) {
oi++;
}
else {
poss = false;
break;
}
}
}
// If poss is true, then we can
// transform a[] to b[]
if (poss)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
// Driver Code
int main()
{
// Given arrays
int arr1[] = { 0, 1, 13, 3, 4, 14, 6 };
int arr2[] = { 0, 1, 14, 3, 4, 13, 6 };
int N = sizeof(arr1) / sizeof(arr1[0]);
// Function Call
convert(arr1, arr2, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function which checks if it is
// possible to convert arr1[] to
// arr2[] by given operations
static void convert(int a[], int b[], int n)
{
// even[] will store the even
// elements of a[]
// odd[] will store the odd
// elements of a[]
Vector<Integer> even = new Vector<Integer>(),
odd = new Vector<Integer>();
// Traverse a[] and insert the even
// and odd element respectively
for(int x = 0; x < n; x++)
{
if (a[x] % 2 == 0)
even.add(a[x]);
else
odd.add(a[x]);
}
// ei points to the next
// available even element
// oi points to the next
// available odd element
int ei = 0, oi = 0;
// poss will store whether the
// given transformation
// of a[] to b[] is possible
boolean poss = true;
// Traverse b[]
for(int x = 0; x < n; x++)
{
if (b[x] % 2 == 0)
{
// Check if both even
// elements are equal
if (ei < even.size() &&
b[x] == even.get(ei))
{
ei++;
}
else
{
poss = false;
break;
}
}
else
{
// Check if both odd
// elements are equal
if (oi < odd.size() &&
b[x] == odd.get(oi))
{
oi++;
}
else
{
poss = false;
break;
}
}
}
// If poss is true, then we can
// transform a[] to b[]
if (poss)
System.out.print("Yes" + "\n");
else
System.out.print("No" + "\n");
}
// Driver Code
public static void main(String[] args)
{
// Given arrays
int arr1[] = { 0, 1, 13, 3, 4, 14, 6 };
int arr2[] = { 0, 1, 14, 3, 4, 13, 6 };
int N = arr1.length;
// Function Call
convert(arr1, arr2, N);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach
# Function which checks if it is
# possible to convert arr1[] to
# arr2[] by given operations
def convert(a, b, n):
# even[] will store the even
# elements of a[]
# odd[] will store the odd
# elements of a[]
even = []
odd = []
# Traverse a[] and insert the even
# and odd element respectively
for x in range(n):
if (a[x] % 2 == 0):
even.append(a[x])
else:
odd.append(a[x])
# ei points to the next
# available even element
# oi points to the next
# available odd element
ei, oi = 0, 0
# poss will store whether the
# given transformation
# of a[] to b[] is possible
poss = True
# Traverse b[]
for x in range(n):
if (b[x] % 2 == 0):
# Check if both even
# elements are equal
if (ei < len(even) and
b[x] == even[ei]):
ei += 1
else:
poss = False
break
else:
# Check if both odd
# elements are equal
if (oi < len(odd) and
b[x] == odd[oi]):
oi += 1
else:
poss = False
break
# If poss is true, then we can
# transform a[] to b[]
if (poss):
print("Yes")
else:
print("No")
# Driver Code
if __name__ == "__main__":
# Given arrays
arr1 = [ 0, 1, 13, 3, 4, 14, 6 ]
arr2 = [ 0, 1, 14, 3, 4, 13, 6 ]
N = len(arr1)
# Function call
convert(arr1, arr2, N)
# This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function which checks if it is
// possible to convert arr1[] to
// arr2[] by given operations
static void convert(int []a, int []b, int n)
{
// even[] will store the even
// elements of []a
// odd[] will store the odd
// elements of []a
List<int> even = new List<int>(),
odd = new List<int>();
// Traverse []a and insert the even
// and odd element respectively
for(int x = 0; x < n; x++)
{
if (a[x] % 2 == 0)
even.Add(a[x]);
else
odd.Add(a[x]);
}
// ei points to the next
// available even element
// oi points to the next
// available odd element
int ei = 0, oi = 0;
// poss will store whether the
// given transformation
// of []a to []b is possible
bool poss = true;
// Traverse []b
for(int x = 0; x < n; x++)
{
if (b[x] % 2 == 0)
{
// Check if both even
// elements are equal
if (ei < even.Count &&
b[x] == even[ei])
{
ei++;
}
else
{
poss = false;
break;
}
}
else
{
// Check if both odd
// elements are equal
if (oi < odd.Count &&
b[x] == odd[oi])
{
oi++;
}
else
{
poss = false;
break;
}
}
}
// If poss is true, then we can
// transform []a to []b
if (poss)
Console.Write("Yes" + "\n");
else
Console.Write("No" + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Given arrays
int []arr1 = { 0, 1, 13, 3, 4, 14, 6 };
int []arr2 = { 0, 1, 14, 3, 4, 13, 6 };
int N = arr1.Length;
// Function call
convert(arr1, arr2, N);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program for the above approach
// Function which checks if it is
// possible to convert arr1[] to
// arr2[] by given operations
function convert(a, b, n)
{
// even[] will store the even
// elements of a[]
// odd[] will store the odd
// elements of a[]
var even = [], odd = [];
// Traverse a[] and insert the even
// and odd element respectively
for (var x = 0; x < n; x++) {
if (a[x] % 2 == 0)
even.push(a[x]);
else
odd.push(a[x]);
}
// ei points to the next
// available even element
// oi points to the next
// available odd element
var ei = 0, oi = 0;
// poss will store whether the
// given transformation
// of a[] to b[] is possible
var poss = true;
// Traverse b[]
for (var x = 0; x < n; x++) {
if (b[x] % 2 == 0) {
// Check if both even
// elements are equal
if (ei < even.length
&& b[x] == even[ei]) {
ei++;
}
else {
poss = false;
break;
}
}
else {
// Check if both odd
// elements are equal
if (oi < odd.length
&& b[x] == odd[oi]) {
oi++;
}
else {
poss = false;
break;
}
}
}
// If poss is true, then we can
// transform a[] to b[]
if (poss)
document.write( "Yes" );
else
document.write( "No" );
}
// Driver Code
// Given arrays
var arr1 = [0, 1, 13, 3, 4, 14, 6 ];
var arr2 = [0, 1, 14, 3, 4, 13, 6 ];
var N = arr1.length;
// Function Call
convert(arr1, arr2, N);
</script>
Producción:
No
Complejidad de tiempo: O(N) , donde N es el número de elementos en la array.
Espacio auxiliar: O(N) , donde N es el número de elementos del arreglo.
Publicación traducida automáticamente
Artículo escrito por shobhitgupta907 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA