Dada una array binaria y un entero m, encuentre la posición del cambio de ceros que crea el número máximo de 1 consecutivos en la array.
Ejemplos:
Input: arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1}
m = 2
Output: 5 7
We are allowed to flip maximum 2 zeroes. If we flip
arr[5] and arr[7], we get 8 consecutive 1's which is
maximum possible under given constraints
Input: arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1}
m = 1
Output: 7
We are allowed to flip maximum 1 zero. If we flip
arr[7], we get 5 consecutive 1's which is maximum
possible under given constraints.
Input: arr[] = {0, 0, 0, 1}
m = 4
Output: 0 1 2
Since m is more than number of zeroes, we can flip
all zeroes.
Una solución simple es considerar cada subarreglo ejecutando dos bucles. Para cada subarreglo, cuente el número de ceros en él. Devuelve el subarreglo de tamaño máximo con m o menos ceros. La complejidad temporal de esta solución es O(n 2 ).
Una mejor solución es utilizar el espacio auxiliar para resolver el problema en tiempo O(n).
Para todas las posiciones de 0, calcule left[] y right[], que define el número de 1 consecutivos a la izquierda de i ya la derecha de i respectivamente.
Por ejemplo, para arr[] = {1, 1, 0, 1, 1, 0, 0, 1, 1, 1} y m = 1, izquierda[2] = 2 y derecha[2] = 2, izquierda[ 5] = 2 y derecha[5] = 0, izquierda[6] = 0 y derecha[6] = 3.
left[] y right[] se pueden completar en tiempo O(n) recorriendo la array una vez y realizando un seguimiento de los últimos 1 y 0 vistos por última vez. Mientras llenamos left[] y right[], también almacenamos índices de todos los ceros en una tercera array dice ceros []. Para el ejemplo anterior, esta tercera array almacena {2, 5, 6}
Ahora recorra zeroes[] y para todas las m entradas consecutivas en esta array, calcule la suma de 1 que se puede producir. Este paso se puede hacer en O(n) usando left[] y right[].
Implementación:
C++
// C++ program to find positions of zeroes flipping which
// produces maximum number of consecutive 1's
#include <bits/stdc++.h>
using namespace std;
// m is maximum of number zeroes allowed to flip
// n is size of array
vector<int> maximized_one(int arr[], int n, int m)
{
// Left array
int left[n] = { 0 };
// Right array
int right[n] = { 0 };
// Array will contain zeroes position
vector<int> zero_pos;
// Stores count
int count = 0;
int previous_index_of_zero = -1;
for (int i = 0; i < n; i++) {
if (arr[i]) {
count++;
}
else {
left[i] = count;
zero_pos.push_back(i);
if (previous_index_of_zero != i
&& previous_index_of_zero != -1) {
right[previous_index_of_zero] = count;
}
count = 0;
// To keep track of the previous index of zeroes
previous_index_of_zero = i;
}
}
right[previous_index_of_zero] = count;
int max_one = -1;
vector<int> result_index;
int i = 0;
while (i <= (zero_pos.size()) - m) {
int temp = 0;
vector<int> index;
for (int c = 0; c < m; c++) {
temp += left[zero_pos[i + c]]
+ right[zero_pos[i + c]] + 1;
// Index is updated
index.push_back(zero_pos[i + c]);
}
// Decrement temp by m-1 because when we are
// calculating temp we are adding 1 in it. So, in
// order to get exact count of 1. This decrement is
// applicable only when value of m is greater than 1
temp = temp - (m - 1);
// Updating max value when we get the new max temp
// and result_index as well
if (temp > max_one) {
max_one = temp;
result_index = index;
}
i += 1;
}
return result_index;
}
// Driver program
int main()
{
int arr[] = { 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1 };
int m = 2;
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Index of zeroes that are flipped: ";
vector<int> result_index = maximized_one(arr, n, m);
for (auto i : result_index) {
cout << i << " ";
}
return 0;
}
Java
// Java program to find positions of zeroes flipping which
// produces maximum number of consecutive 1's
import java.util.*;
class GFG{
// m is maximum of number zeroes allowed to flip
// n is size of array
static Vector<Integer> maximized_one(int arr[], int n, int m)
{
// Left array
int left[] = new int[n];
// Right array
int right[] = new int[n];
// Array will contain zeroes position
Vector<Integer> zero_pos = new Vector<>();
// Stores count
int count = 0;
int previous_index_of_zero = -1;
for (int i = 0; i < n; i++) {
if (arr[i]!=0) {
count++;
}
else {
left[i] = count;
zero_pos.add(i);
if (previous_index_of_zero != i
&& previous_index_of_zero != -1) {
right[previous_index_of_zero] = count;
}
count = 0;
// To keep track of the previous index of zeroes
previous_index_of_zero = i;
}
}
right[previous_index_of_zero] = count;
int max_one = -1;
Vector<Integer> result_index = new Vector<>();
int i = 0;
while (i <= (zero_pos.size()) - m) {
int temp = 0;
Vector<Integer> index = new Vector<>();
for (int c = 0; c < m; c++) {
temp += left[zero_pos.elementAt(i + c)]
+ right[zero_pos.elementAt(i + c)] + 1;
// Index is updated
index.add(zero_pos.elementAt(i + c));
}
// Decrement temp by m-1 because when we are
// calculating temp we are adding 1 in it. So, in
// order to get exact count of 1. This decrement is
// applicable only when value of m is greater than 1
temp = temp - (m - 1);
// Updating max value when we get the new max temp
// and result_index as well
if (temp > max_one) {
max_one = temp;
result_index = index;
}
i += 1;
}
return result_index;
}
// Driver program
public static void main(String[] args)
{
int arr[] = { 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1 };
int m = 2;
int n = arr.length;
System.out.print("Index of zeroes that are flipped: [");
Vector<Integer> result_index = maximized_one(arr, n, m);
for (int i : result_index) {
System.out.print(i+ " ");
}
System.out.print("]");
}
}
// This code contributed by umadevi9616
Python3
# Python3 code for the above approach
def maximized_one(arr,n,m):
# Left array
left = [0]*n
# Right array
right = [0]*n
# Array will contain zeroes position
zero_pos = []
# Stores count
count = 0
previous_index_of_zero = -1
for i in range(n):
if arr[i] == 1:
count+=1
if arr[i] == 0:
left[i] = count
zero_pos.append(i)
if previous_index_of_zero !=i and previous_index_of_zero!=-1:
right[previous_index_of_zero] = count
count = 0
# To keep track of the previous index of zeroes
previous_index_of_zero = i
right[previous_index_of_zero] = count
# print(left)
# print(right)
# print(zero_pos)
max_one = -1
result_index = 0
i=0
while(i<=len(zero_pos)-m):
temp = 0
index = []
for c in range(m):
# print(zero_pos[i+c],left[zero_pos[i+c]],right[zero_pos[i+c]])
temp += left[zero_pos[i+c]] + right[zero_pos[i+c]] +1
# Index is updated
index.append(zero_pos[i+c])
# Decrement temp by m-1 because when we are calculating temp
# we are adding 1 in it.
# So, in order to get exact count of 1.
# This decrement is applicable only when value of m is greater than 1
temp = temp-(m-1)
# Updating max value when we get the new max temp
# and result_index as well
if temp > max_one:
max_one = temp
result_index = index
i+=1
return result_index
# Driver Code
if __name__ == '__main__':
arr = [1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1]
n = len(arr)
m = 2
print('Index of zeroes that are flipped: ',maximized_one(arr,n,m))
C#
// C# program to find positions of zeroes flipping which
// produces maximum number of consecutive 1's
using System;
using System.Collections.Generic;
public class GFG
{
// m is maximum of number zeroes allowed to flip
// n is size of array
static List<int> maximized_one(int []arr, int n, int m)
{
// Left array
int []left = new int[n];
// Right array
int []right = new int[n];
// Array will contain zeroes position
List<int> zero_pos = new List<int>();
// Stores count
int count = 0;
int previous_index_of_zero = -1;
for (int j = 0; j < n; j++) {
if (arr[j] != 0) {
count++;
}
else {
left[j] = count;
zero_pos.Add(j);
if (previous_index_of_zero != j
&& previous_index_of_zero != -1) {
right[previous_index_of_zero] = count;
}
count = 0;
// To keep track of the previous index of zeroes
previous_index_of_zero = j;
}
}
right[previous_index_of_zero] = count;
int max_one = -1;
List<int> result_index = new List<int>();
int i = 0;
while (i <= (zero_pos.Count) - m) {
int temp = 0;
List<int> index = new List<int>();
for (int c = 0; c < m; c++) {
temp += left[zero_pos[i + c]]
+ right[zero_pos[i + c]] + 1;
// Index is updated
index.Add(zero_pos[i + c]);
}
// Decrement temp by m-1 because when we are
// calculating temp we are adding 1 in it. So, in
// order to get exact count of 1. This decrement is
// applicable only when value of m is greater than 1
temp = temp - (m - 1);
// Updating max value when we get the new max temp
// and result_index as well
if (temp > max_one) {
max_one = temp;
result_index = index;
}
i += 1;
}
return result_index;
}
// Driver program
public static void Main(String[] args)
{
int []arr = { 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1 };
int m = 2;
int n = arr.Length;
Console.Write("Index of zeroes that are flipped: [");
List<int> result_index = maximized_one(arr, n, m);
foreach (int i in result_index) {
Console.Write(i+ " ");
}
Console.Write("]");
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// javascript program to find positions of zeroes flipping which
// produces maximum number of consecutive 1's
// m is maximum of number zeroes allowed to flip
// n is size of array
function maximized_one(arr, n, m)
{
// Left array
var left = Array(n).fill(0);
// Right array
var right = Array(n).fill(0);
// Array will contain zeroes position
var zero_pos = new Array();
// Stores count
var count = 0;
var previous_index_of_zero = -1;
for (var i = 0; i < n; i++) {
if (arr[i] != 0) {
count++;
} else {
left[i] = count;
zero_pos.push(i);
if (previous_index_of_zero != i && previous_index_of_zero != -1) {
right[previous_index_of_zero] = count;
}
count = 0;
// To keep track of the previous index of zeroes
previous_index_of_zero = i;
}
}
right[previous_index_of_zero] = count;
var max_one = -1;
var result_index = Array();
var i = 0;
while (i <= (zero_pos.length) - m) {
var temp = 0;
var index = Array();
for (var c = 0; c < m; c++)
{
temp += left[zero_pos[i + c]] + right[zero_pos[i + c]] + 1;
// Index is updated
index.push(zero_pos[i + c]);
}
// Decrement temp by m-1 because when we are
// calculating temp we are adding 1 in it. So, in
// order to get exact count of 1. This decrement is
// applicable only when value of m is greater than 1
temp = temp - (m - 1);
// Updating max value when we get the new max temp
// and result_index as well
if (temp > max_one) {
max_one = temp;
result_index = index;
}
i += 1;
}
return result_index;
}
// Driver program
var arr = [ 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1 ];
var m = 2;
var n = arr.length;
document.write("Index of zeroes that are flipped: [");
var result_index = maximized_one(arr, n, m);
for (var i = 0; i < result_index.length; i++) {
document.write(result_index[i] + " ");
}
document.write("]");
// This code is contributed by gauravrajput1
</script>
Producción
Index of zeroes that are flipped: [5, 7]
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Una Solución Eficiente puede resolver el problema en O(n) tiempo y O(1) espacio. La idea es usar Sliding Window para la array dada.
Usemos una cubierta de ventana desde el índice wL hasta el índice wR. Deje que el número de ceros dentro de la ventana sea zeroCount. Mantenemos la ventana con como máximo m ceros dentro.
Los pasos principales son:
- Mientras zeroCount no es más que m: expanda la ventana a la derecha (wR++) y actualice el conteo zeroCount.
- Mientras zeroCount excede m, reduzca la ventana desde la izquierda (wL++), actualice zeroCount;
- Actualice la ventana más ancha en el camino. Las posiciones de los ceros de salida están dentro de la mejor ventana.
A continuación se muestra la implementación de la idea.
C++
// C++ program to find positions of zeroes flipping which
// produces maximum number of consecutive 1's
#include<bits/stdc++.h>
using namespace std;
// m is maximum of number zeroes allowed to flip
// n is size of array
void findZeroes(int arr[], int n, int m)
{
// Left and right indexes of current window
int wL = 0, wR = 0;
// Left index and size of the widest window
int bestL = 0, bestWindow = 0;
// Count of zeroes in current window
int zeroCount = 0;
// While right boundary of current window doesn't cross
// right end
while (wR < n)
{
// If zero count of current window is less than m,
// widen the window toward right
if (zeroCount <= m)
{
if (arr[wR] == 0)
zeroCount++;
wR++;
}
// If zero count of current window is more than m,
// reduce the window from left
if (zeroCount > m)
{
if (arr[wL] == 0)
zeroCount--;
wL++;
}
// Update widest window if this window size is more
if ((wR-wL > bestWindow) && (zeroCount<=m))
{
bestWindow = wR-wL;
bestL = wL;
}
}
// Print positions of zeroes in the widest window
for (int i=0; i<bestWindow; i++)
{
if (arr[bestL+i] == 0)
cout << bestL+i << " ";
}
}
// Driver program
int main()
{
int arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1};
int m = 2;
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Indexes of zeroes to be flipped are ";
findZeroes(arr, n, m);
return 0;
}
Java
//Java to find positions of zeroes flipping which
// produces maximum number of consecutive 1's
class Test
{
static int arr[] = new int[]{1, 0, 0, 1, 1, 0, 1, 0, 1, 1};
// m is maximum of number zeroes allowed to flip
static void findZeroes(int m)
{
// Left and right indexes of current window
int wL = 0, wR = 0;
// Left index and size of the widest window
int bestL = 0, bestWindow = 0;
// Count of zeroes in current window
int zeroCount = 0;
// While right boundary of current window doesn't cross
// right end
while (wR < arr.length)
{
// If zero count of current window is less than m,
// widen the window toward right
if (zeroCount <= m)
{
if (arr[wR] == 0)
zeroCount++;
wR++;
}
// If zero count of current window is more than m,
// reduce the window from left
if (zeroCount > m)
{
if (arr[wL] == 0)
zeroCount--;
wL++;
}
// Update widest window if this window size is more
if ((wR-wL > bestWindow) && (zeroCount<=m))
{
bestWindow = wR-wL;
bestL = wL;
}
}
// Print positions of zeroes in the widest window
for (int i=0; i<bestWindow; i++)
{
if (arr[bestL+i] == 0)
System.out.print(bestL+i + " ");
}
}
// Driver method to test the above function
public static void main(String[] args)
{
int m = 2;
System.out.println("Indexes of zeroes to be flipped are ");
findZeroes(m);
}
}
Python3
# Python3 program to find positions
# of zeroes flipping which produces
# maximum number of consecutive 1's
# m is maximum of number zeroes allowed
# to flip, n is size of array
def findZeroes(arr, n, m) :
# Left and right indexes of current window
wL = wR = 0
# Left index and size of the widest window
bestL = bestWindow = 0
# Count of zeroes in current window
zeroCount = 0
# While right boundary of current
# window doesn't cross right end
while wR < n:
# If zero count of current window is less than m,
# widen the window toward right
if zeroCount <= m :
if arr[wR] == 0 :
zeroCount += 1
wR += 1
# If zero count of current window is more than m,
# reduce the window from left
if zeroCount > m :
if arr[wL] == 0 :
zeroCount -= 1
wL += 1
# Update widest window if
# this window size is more
if (wR-wL > bestWindow) and (zeroCount<=m) :
bestWindow = wR - wL
bestL = wL
# Print positions of zeroes
# in the widest window
for i in range(0, bestWindow):
if arr[bestL + i] == 0:
print (bestL + i, end = " ")
# Driver program
arr = [1, 0, 0, 1, 1, 0, 1, 0, 1, 1]
m = 2
n = len(arr)
print ("Indexes of zeroes to be flipped are", end = " ")
findZeroes(arr, n, m)
# This code is contributed by Shreyanshi Arun.
C#
// C# to find positions of zeroes flipping which
// produces maximum number of consecutive 1's
using System;
class Test
{
static int []arr = new int[]{1, 0, 0, 1, 1,
0, 1, 0, 1, 1};
// m is maximum of number zeroes allowed to flip
static void findZeroes(int m)
{
// Left and right indexes of current window
int wL = 0, wR = 0;
// Left index and size of the widest window
int bestL = 0, bestWindow = 0;
// Count of zeroes in current window
int zeroCount = 0;
// While right boundary of current
// window doesn't cross right end
while (wR < arr.Length)
{
// If zero count of current window is less
// than m, widen the window toward right
if (zeroCount <= m)
{
if (arr[wR] == 0)
zeroCount++;
wR++;
}
// If zero count of current window is more than m,
// reduce the window from left
if (zeroCount > m)
{
if (arr[wL] == 0)
zeroCount--;
wL++;
}
// Update widest window if this window size is more
if ((wR-wL > bestWindow) && (zeroCount<=m))
{
bestWindow = wR-wL;
bestL = wL;
}
}
// Print positions of zeroes in the widest window
for (int i = 0; i < bestWindow; i++)
{
if (arr[bestL + i] == 0)
Console.Write(bestL + i + " ");
}
}
// Driver method to test the above function
public static void Main(String[] args)
{
int m = 2;
Console.Write("Indexes of zeroes to be flipped are ");
findZeroes(m);
}
}
// This code is contributed by parashar
PHP
<?php
// PHP program to find positions of
// zeroes flipping which produces
// maximum number of consecutive 1's
// m is maximum of number zeroes
// allowed to flip n is size of array
function findZeroes($arr, $n, $m)
{
// Left and right indexes
// of current window
$wL = 0;
$wR = 0;
// Left index and size of
// the widest window
$bestL = 0;
$bestWindow = 0;
// Count of zeroes in
// current window
$zeroCount = 0;
// While right boundary of
// current window doesn't cross
// right end
while ($wR < $n)
{
// If zero count of current
// window is less than m,
// widen the window toward right
if ($zeroCount <= $m)
{
if ($arr[$wR] == 0)
$zeroCount++;
$wR++;
}
// If zero count of current
// window is more than m,
// reduce the window from left
if ($zeroCount > $m)
{
if ($arr[$wL] == 0)
$zeroCount--;
$wL++;
}
// Update widest window if
// this window size is more
if (($wR-$wL > $bestWindow) && ($zeroCount<=$m))
{
$bestWindow = $wR - $wL;
$bestL = $wL;
}
}
// Print positions of zeroes
// in the widest window
for($i = 0; $i < $bestWindow; $i++)
{
if ($arr[$bestL + $i] == 0)
echo $bestL + $i . " ";
}
}
// Driver Code
$arr = array(1, 0, 0, 1, 1, 0, 1, 0, 1, 1);
$m = 2;
$n = sizeof($arr)/sizeof($arr[0]);
echo "Indexes of zeroes to be flipped are ";
findZeroes($arr, $n, $m);
return 0;
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// Javascript program to find positions of
// zeroes flipping which produces
// maximum number of consecutive 1's
// m is maximum of number zeroes
// allowed to flip n is size of array
function findZeroes(arr, n, m) {
// Left and right indexes
// of current window
let wL = 0;
let wR = 0;
// Left index and size of
// the widest window
let bestL = 0;
let bestWindow = 0;
// Count of zeroes in
// current window
let zeroCount = 0;
// While right boundary of
// current window doesn't cross
// right end
while (wR < n) {
// If zero count of current
// window is less than m,
// widen the window toward right
if (zeroCount <= m) {
if (arr[wR] == 0)
zeroCount++;
wR++;
}
// If zero count of current
// window is more than m,
// reduce the window from left
if (zeroCount > m) {
if (arr[wL] == 0)
zeroCount--;
wL++;
}
// Update widest window if
// this window size is more
if ((wR - wL > bestWindow) && (zeroCount <= m)) {
bestWindow = wR - wL;
bestL = wL;
}
}
// Print positions of zeroes
// in the widest window
for (let i = 0; i < bestWindow; i++) {
if (arr[bestL + i] == 0)
document.write(bestL + i + " ");
}
}
// Driver Code
let arr = new Array(1, 0, 0, 1, 1, 0, 1, 0, 1, 1);
let m = 2;
let n = arr.length;
document.write("Indexes of zeroes to be flipped are ");
findZeroes(arr, n, m);
// This code is contributed by Saurabh Jaiswal
</script>
Producción
Indexes of zeroes to be flipped are 5 7
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA