Dado el tamaño de una array binaria que consta de 0 solo como n y un número entero m , que es el número de vueltas permitidas de 0 a 1; la tarea es maximizar la distancia entre dos 1 consecutivos después de convertir m 0 en 1.
Ejemplos:
Entrada: n = 5, m = 3
Salida: 2
Explicación:
La array inicial es arr = {0, 0, 0, 0, 0},
La array final es arr = {1, 0, 1, 0, 1},
Entonces, la distancia entre dos 1 consecutivos es 2.
Entrada: n = 9, m = 3
Salida: 4
Explicación:
La array inicial es arr = {0, 0, 0, 0, 0, 0, 0, 0, 0},
The la array final es arr = {1, 0, 0, 0, 1, 0, 0, 0, 1},
por lo que la distancia entre dos 1 consecutivos es 4.
Acercarse:
- Simplemente podemos realizar una búsqueda binaria en la distancia entre dos cualesquiera consecutivos y verificar si podemos cambiar m números de ceros a uno.
- Primero, establecemos bajo = 1 y alto = n – 1,
- Luego verifique si mid = (low+high)/2 será una distancia adecuada o no.
- Si es así, la respuesta actualizada es mid, de lo contrario, disminuya high = mid – 1.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to Maximize distance between
// any two consecutive 1's after flipping M 0's
#include <bits/stdc++.h>
using namespace std;
// Function to return the count
bool check(int arr[], int n, int m, int d)
{
// Flipping zeros at distance "d"
int i = 0;
while (i < n && m > 0) {
m--;
i += d;
}
return m == 0 ? true : false;
}
// Function to implement
// binary search
int maximumDistance(int arr[], int n, int m)
{
int low = 1, high = n - 1;
int ans = 0;
while (low <= high) {
int mid = (low + high) / 2;
// Check for valid distance i.e mid
bool flag = check(arr, n, m, mid);
if (flag) {
ans = mid;
low = mid + 1;
}
else {
high = mid - 1;
}
}
return ans;
}
// Driver code
int main()
{
int n = 5, m = 3;
int arr[n] = { 0 };
cout << maximumDistance(arr, n, m);
return 0;
}
Java
// Java program to Maximize distance between
// any two consecutive 1's after flipping M 0's
class GFG
{
// Function to return the count
static boolean check(int arr[], int n, int m, int d)
{
// Flipping zeros at distance "d"
int i = 0;
while (i < n && m > 0)
{
m--;
i += d;
}
return m == 0 ? true : false;
}
// Function to implement
// binary search
static int maximumDistance(int arr[], int n, int m)
{
int low = 1, high = n - 1;
int ans = 0;
while (low <= high)
{
int mid = (low + high) / 2;
// Check for valid distance i.e mid
boolean flag = check(arr, n, m, mid);
if (flag)
{
ans = mid;
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int n = 5, m = 3;
int arr[] = new int[n];
System.out.print(maximumDistance(arr, n, m));
}
}
// This code is contributed by 29AjayKumar
Python
# Python3 program to Maximize distance between # any two consecutive 1's after flipping M 0's # Function to return the count def check(arr, n, m, d): # Flipping zeros at distance "d" i = 0 while (i < n and m > 0): m -= 1 i += d if m == 0: return True return False # Function to implement # binary search def maximumDistance(arr, n, m): low = 1 high = n - 1 ans = 0 while (low <= high): mid = (low + high) // 2 # Check for valid distance i.e mid flag = check(arr, n, m, mid) if (flag) : ans = mid low = mid + 1 else : high = mid - 1 return ans # Driver code n = 5 m = 3 arr = [0] * n print(maximumDistance(arr, n, m)) # This code is contributed by mohit kumar 29
C#
// C# program to Maximize distance between
// any two consecutive 1's after flipping M 0's
using System;
class GFG
{
// Function to return the count
static bool check(int []arr, int n, int m, int d)
{
// Flipping zeros at distance "d"
int i = 0;
while (i < n && m > 0)
{
m--;
i += d;
}
return m == 0 ? true : false;
}
// Function to implement
// binary search
static int maximumDistance(int []arr, int n, int m)
{
int low = 1, high = n - 1;
int ans = 0;
while (low <= high)
{
int mid = (low + high) / 2;
// Check for valid distance i.e mid
bool flag = check(arr, n, m, mid);
if (flag)
{
ans = mid;
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int n = 5, m = 3;
int []arr = new int[n];
Console.Write(maximumDistance(arr, n, m));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
//Javascript program to Maximize distance between
// any two consecutive 1's after flipping M 0's
// Function to return the count
function check(arr, n, m, d)
{
// Flipping zeros at distance "d"
var i = 0;
while (i < n && m > 0) {
m--;
i += d;
}
return m == 0 ? true : false;
}
// Function to implement
// binary search
function maximumDistance(arr, n, m)
{
var low = 1, high = n - 1;
var ans = 0;
while (low <= high) {
var mid = parseInt( (low + high) / 2);
// Check for valid distance i.e mid
var flag = check(arr, n, m, mid);
if (flag) {
ans = mid;
low = mid + 1;
}
else {
high = mid - 1;
}
}
return ans;
}
var n = 5, m = 3;
var arr = new Array(n);
arr.fill(0);
document.write( maximumDistance(arr, n, m));
//This code is contributed by SoumikMondal
</script>
Producción:
2
Complejidad del tiempo: O(n*log(n))
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA