Dados dos arreglos binarios X[] e Y[] de tamaño N , la tarea es convertir el arreglo X[] en el arreglo Y[] mediante un número mínimo de operaciones de selección de cualquier subarreglo de longitud impar y volteando todos los elementos impares indexados del subarreglo
Ejemplos:
Entrada: X[] = {1, 0, 0, 0, 0, 1}, Y[] = {1, 1, 0, 1, 1, 1}
Salida: 2
Explicación:
Inicialmente, X[] es {1 , 0, 0, 0, 0, 1}.
Operación 1: Elija la sub-array {0, 0, 0} de la array X[] y cambie el 2º y 4º carácter y conviértalo a {1, 0, 1}.
Ahora X se convierte en {1, 1, 0, 1, 0, 1}.
Operación 2: Elija la sub-array {0} que contiene solo el quinto carácter y conviértala en 1.
Finalmente, X se convierte en {1, 1, 0, 1, 1, 1}, que es igual a Y.
Por lo tanto, la cuenta de operaciones es 2.Entrada: X[] = {0, 1, 0}, Y[] = {0, 1, 0}
Salida: 0
Explicación:
Dado que las arrays X e Y son iguales, las operaciones mínimas serían 0.
Enfoque: La idea es contar las operaciones para posiciones pares e impares individualmente. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable C como 0 para almacenar el recuento de operaciones.
- Recorra los elementos del arreglo X[] sobre posiciones impares y tome un conteo de contadores = 0.
- Compruebe si hay elementos desiguales consecutivos entre X[i] e Y[i] y aumente la cuenta del contador en 1 cada vez.
- Cuando X[i] e Y[i] son iguales, aumente una C global para aumentar la operación en 1, ya que en esa operación todas las posiciones impares pueden igualarse como en Y .
- De manera similar, recorra los elementos de la array X[] en posiciones pares y nuevamente tome una cuenta de contador = 0.
- Compruebe si hay elementos desiguales consecutivos entre X[i] e Y[i] y aumente la cuenta del contador en 1 cada vez.
- Cuando X[i] e Y[i] son iguales, aumente un contador global C para aumentar la operación en 1 .
- Después de los pasos anteriores, imprima el valor de C como el conteo resultante de las operaciones requeridas.
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 the minimum flip
// of subarrays required at alternate
// index to make binary arrays equals
void minOperation(int X[], int Y[],
int n)
{
// Stores count of total operations
int C = 0;
// Stores count of consecutive
// unequal elements
int count = 0;
// Loop to run on odd positions
for (int i = 1; i < n; i = i + 2) {
if (X[i] != Y[i]) {
count++;
}
else {
// Incrementing the
// global counter
if (count != 0)
C++;
// Change count to 0
count = 0;
}
}
// If all last elements are equal
if (count != 0)
C++;
count = 0;
// Loop to run on even positions
for (int i = 0; i < n; i = i + 2) {
if (X[i] != Y[i]) {
count++;
}
else {
// Incrementing the
// global counter
if (count != 0)
C++;
// Change count to 0
count = 0;
}
}
if (count != 0)
C++;
// Print the minimum operations
cout << C;
}
// Driver Code
int main()
{
int X[] = { 1, 0, 0, 0, 0, 1 };
int Y[] = { 1, 1, 0, 1, 1, 1 };
int N = sizeof(X) / sizeof(X[0]);
// Function Call
minOperation(X, Y, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the minimum flip
// of subarrays required at alternate
// index to make binary arrays equals
static void minOperation(int X[], int Y[],
int n)
{
// Stores count of total operations
int C = 0;
// Stores count of consecutive
// unequal elements
int count = 0;
// Loop to run on odd positions
for(int i = 1; i < n; i = i + 2)
{
if (X[i] != Y[i])
{
count++;
}
else
{
// Incrementing the
// global counter
if (count != 0)
C++;
// Change count to 0
count = 0;
}
}
// If all last elements are equal
if (count != 0)
C++;
count = 0;
// Loop to run on even positions
for(int i = 0; i < n; i = i + 2)
{
if (X[i] != Y[i])
{
count++;
}
else
{
// Incrementing the
// global counter
if (count != 0)
C++;
// Change count to 0
count = 0;
}
}
if (count != 0)
C++;
// Print the minimum operations
System.out.print(C);
}
// Driver Code
public static void main(String[] args)
{
int X[] = { 1, 0, 0, 0, 0, 1 };
int Y[] = { 1, 1, 0, 1, 1, 1 };
int N = X.length;
// Function Call
minOperation(X, Y, N);
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python program for the above approach # Function to find the minimum flip # of subarrays required at alternate # index to make binary arrays equals def minOperation(X, Y, n): # Stores count of total operations C = 0; # Stores count of consecutive # unequal elements count = 0; # Loop to run on odd positions for i in range(1, n, 2): if (X[i] != Y[i]): count += 1; else: # Incrementing the # global counter if (count != 0): C += 1; # Change count to 0 count = 0; # If all last elements are equal if (count != 0): C += 1; count = 0; # Loop to run on even positions for i in range(0, n, 2): if (X[i] != Y[i]): count += 1; else: # Incrementing the # global counter if (count != 0): C += 1; # Change count to 0 count = 0; if (count != 0): C += 1; # Print minimum operations print(C); # Driver Code if __name__ == '__main__': X = [1, 0, 0, 0, 0, 1]; Y = [1, 1, 0, 1, 1, 1]; N = len(X); # Function Call minOperation(X, Y, N); # This code is contributed by 29AjayKumar
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum flip
// of subarrays required at alternate
// index to make binary arrays equals
static void minOperation(int []X, int []Y,
int n)
{
// Stores count of total operations
int C = 0;
// Stores count of consecutive
// unequal elements
int count = 0;
// Loop to run on odd positions
for(int i = 1; i < n; i = i + 2)
{
if (X[i] != Y[i])
{
count++;
}
else
{
// Incrementing the
// global counter
if (count != 0)
C++;
// Change count to 0
count = 0;
}
}
// If all last elements are equal
if (count != 0)
C++;
count = 0;
// Loop to run on even positions
for(int i = 0; i < n; i = i + 2)
{
if (X[i] != Y[i])
{
count++;
}
else
{
// Incrementing the
// global counter
if (count != 0)
C++;
// Change count to 0
count = 0;
}
}
if (count != 0)
C++;
// Print the minimum operations
Console.Write(C);
}
// Driver Code
public static void Main(String[] args)
{
int []X = { 1, 0, 0, 0, 0, 1 };
int []Y = { 1, 1, 0, 1, 1, 1 };
int N = X.Length;
// Function Call
minOperation(X, Y, N);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// javascript program to implement
// the above approach
// Function to find the minimum flip
// of subarrays required at alternate
// index to make binary arrays equals
function minOperation(X, Y,
n)
{
// Stores count of total operations
let C = 0;
// Stores count of consecutive
// unequal elements
let count = 0;
// Loop to run on odd positions
for(let i = 1; i < n; i = i + 2)
{
if (X[i] != Y[i])
{
count++;
}
else
{
// Incrementing the
// global counter
if (count != 0)
C++;
// Change count to 0
count = 0;
}
}
// If all last elements are equal
if (count != 0)
C++;
count = 0;
// Loop to run on even positions
for(let i = 0; i < n; i = i + 2)
{
if (X[i] != Y[i])
{
count++;
}
else
{
// Incrementing the
// global counter
if (count != 0)
C++;
// Change count to 0
count = 0;
}
}
if (count != 0)
C++;
// Print the minimum operations
document.write(C);
}
// Driver code
let X = [ 1, 0, 0, 0, 0, 1 ];
let Y = [ 1, 1, 0, 1, 1, 1 ];
let N = X.length;
// Function Call
minOperation(X, Y, N);
// This code is contributed by splevel62.
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por mishrapriyanshu557 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA