Dada una array binaria, necesitamos convertir esta array en una array que contenga solo 1 o solo 0. Tenemos que hacerlo usando el número mínimo de volteretas de grupo.
Ejemplos:
Entrada : arr[] = {1, 1, 0, 0, 0, 1}
Salida : De 2 a 4
Explicación : Tenemos dos opciones, hacemos todos 0 o hacemos todos 1. Necesitamos hacer dos cambios de grupo para hacer que todos los elementos sean 0 y un cambio de grupo para hacer que todos los elementos sean 1. Dado que hacer que todos los elementos sean 1 requiere menos cambios de grupo, hacemos esto.
Entrada : arr[] = {1, 0, 0, 0, 1, 0, 0, 1, 0, 1}
Salida :
De 1 a 3
De 5 a 6
De 8 a 8
Entrada : arr[] = {0, 0, 0}
Salida :
Explicación : La salida está vacía, no necesitamos hacer ningún cambio
Entrada : arr[] = {1, 1, 1}
Salida :
Explicación: La salida está vacía, no necesitamos hacer ningún cambio
Entrada : arr[] = {0, 1}
Salida :
De 0 a 0
O
de 1 a 1
Explicación : Aquí el número de vueltas es el mismo, hacemos todos los elementos como 1 o todos los elementos como 0.
Una solución ingenua es atravesar hacer dos recorridos de la array. Primero recorremos para encontrar el número de grupos de 0 y el número de grupos de 1. Encontramos el mínimo de estos dos. Luego recorremos la array y volteamos los 1 si los grupos de 1 son menores. De lo contrario, volteamos 0s.
¿Cómo hacerlo con un recorrido de array?
Una solución eficiente se basa en los siguientes hechos:
- Solo hay dos tipos de grupos (grupos de 0s y grupos de 1s)
- O los recuentos de ambos grupos son iguales o la diferencia entre los recuentos es como máximo 1. Por ejemplo, en {1, 1, 0, 1, 0, 0} hay dos grupos de 0 y dos grupos de 1. En el ejemplo, {1, 1, 0, 0, 0, 1, 0, 0, 1, 1}, el conteo de grupos de 1 es uno más que el conteo de 0s.
Con base en los hechos anteriores, podemos concluir que si siempre volteamos el segundo grupo y otros grupos del mismo tipo que el segundo grupo, siempre obtendremos la respuesta correcta. En el primer caso, cuando el conteo de grupos es el mismo, no importa qué tipo de grupo volteemos, ya que ambos conducirán a la respuesta correcta. En el segundo caso, cuando hay uno extra, al ignorar el primer grupo y comenzar desde el segundo grupo, convertimos este caso en el primer caso (para el subarreglo que comienza desde el segundo grupo) y obtenemos la respuesta correcta.
C++
// C++ program to find the minimum
// group flips in a binary array
#include <iostream>
using namespace std;
void printGroups(bool arr[], int n) {
// Traverse through all array elements
// starting from the second element
for (int i = 1; i < n; i++) {
// If current element is not same
// as previous
if (arr[i] != arr[i - 1]) {
// If it is same as first element
// then it is starting of the interval
// to be flipped.
if (arr[i] != arr[0])
cout << "From " << i << " to ";
// If it is not same as previous
// and same as first element, then
// previous element is end of interval
else
cout << (i - 1) << endl;
}
}
// Explicitly handling the end of
// last interval
if (arr[n - 1] != arr[0])
cout << (n - 1) << endl;
}
int main() {
bool arr[] = {0, 1, 1, 0, 0, 0, 1, 1};
int n = sizeof(arr) / sizeof(arr[0]);
printGroups(arr, n);
return 0;
}
Java
// Java program to find the minimum
// group flips in a binary array
import java.io.*;
import java.util.*;
class GFG {
static void printGroups(int arr[], int n)
{
// Traverse through all array elements
// starting from the second element
for(int i = 1; i < n; i++)
{
// If current element is not same
// as previous
if (arr[i] != arr[i - 1])
{
// If it is same as first element
// then it is starting of the interval
// to be flipped.
if (arr[i] != arr[0])
System.out.print("From " + i + " to ");
// If it is not same as previous
// and same as first element, then
// previous element is end of interval
else
System.out.println(i - 1);
}
}
// Explicitly handling the end of
// last interval
if (arr[n - 1] != arr[0])
System.out.println(n - 1);
}
// Driver code
public static void main(String[] args)
{
int arr[] = {0, 1, 1, 0, 0, 0, 1, 1};
int n = arr.length;
printGroups(arr, n);
}
}
// This code is contributed by coder001
Python3
# Python3 program to find the minimum
# group flips in a binary array
def printGroups(arr, n):
# Traverse through all array elements
# starting from the second element
for i in range(1, n):
# If current element is not same
# as previous
if (arr[i] != arr[i - 1]):
# If it is same as first element
# then it is starting of the interval
# to be flipped.
if (arr[i] != arr[0]):
print("From", i, "to ", end = "")
# If it is not same as previous
# and same as the first element, then
# previous element is end of interval
else:
print(i - 1)
# Explicitly handling the end of
# last interval
if (arr[n - 1] != arr[0]):
print(n - 1)
# Driver Code
if __name__ == '__main__':
arr = [ 0, 1, 1, 0, 0, 0, 1, 1 ]
n = len(arr)
printGroups(arr, n)
# This code is contributed by Bhupendra_Singh
C#
// C# program to find the minimum
// group flips in a binary array
using System;
class GFG{
static void printGroups(int []arr, int n)
{
// Traverse through all array elements
// starting from the second element
for(int i = 1; i < n; i++)
{
// If current element is not same
// as previous
if (arr[i] != arr[i - 1])
{
// If it is same as first element
// then it is starting of the interval
// to be flipped.
if (arr[i] != arr[0])
Console.Write("From " + i + " to ");
// If it is not same as previous
// and same as first element, then
// previous element is end of interval
else
Console.WriteLine(i - 1);
}
}
// Explicitly handling the end
// of last interval
if (arr[n - 1] != arr[0])
Console.WriteLine(n - 1);
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 0, 1, 1, 0, 0, 0, 1, 1 };
int n = arr.Length;
printGroups(arr, n);
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// JavaScript program to find the minimum
// group flips in a binary array
function printGroups(arr, n) {
// Traverse through all array elements
// starting from the second element
for (var i = 1; i < n; i++) {
// If current element is not same
// as previous
if (arr[i] != arr[i - 1]) {
// If it is same as first element
// then it is starting of the interval
// to be flipped.
if (arr[i] != arr[0])
document.write( "From " + i + " to ");
// If it is not same as previous
// and same as first element, then
// previous element is end of interval
else
document.write(i - 1 + "<br>");
}
}
// Explicitly handling the end of
// last interval
if (arr[n - 1] != arr[0])
document.write(n - 1 + "<br>");
}
var arr = [0, 1, 1, 0, 0, 0, 1, 1];
var n = arr.length;
printGroups(arr, n);
</script>
From 1 to 2 From 6 to 7
Complejidad temporal: O(n)
Espacio auxiliar: O(1)