Dada una array circular binaria arr[] de tamaño N , la tarea es encontrar los intercambios mínimos para agrupar todos los 0 en la array.
Ejemplos :
Entrada: arr[] = {1, 0, 1, 0, 0, 1, 1}
Salida: 1
Explicación: Estas son algunas de las formas de agrupar todos los 0:
- {1, 1, 0, 0, 0, 1, 1} usando 1 intercambio.
- {1, 0, 0, 0, 1, 1, 1} usando 1 intercambio.
- {0, 0, 1, 1, 1, 1, 0} usando 2 intercambios (usando la propiedad circular de la array).
No hay forma de agrupar todos los 0 junto con 0 intercambios. Por lo tanto, el número mínimo de intercambios necesarios es 1.
Entrada: arr[] = {0, 0, 1, 1, 0}
Salida: 0
Explicación: Todos los 0 ya están agrupados debido a la propiedad circular de la array.
Por lo tanto, el número mínimo de intercambios requeridos es 0.
Enfoque: La tarea se puede resolver utilizando la técnica de la ventana deslizante . Siga los pasos a continuación para resolver el problema:
- Cuente el número total de 0s. Sea m ese numero
- Encuentre la región contigua de longitud m que tiene la mayor cantidad de ceros en ella
- El número de 1 en esta región es el intercambio mínimo requerido. Cada intercambio moverá un 0 a la región y un 1 fuera de la región.
- Finalmente, use la operación de módulo para manejar el caso de las arrays circulares.
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 count min swap
// to get all zeros together
int minSwaps(int nums[], int N)
{
int count_1 = 0;
if (N == 1)
return 0;
for (int i = 0; i < N; i++) {
if (nums[i] == 0)
count_1++;
}
// Window size for counting
// maximum no. of 1s
int windowsize = count_1;
count_1 = 0;
for (int i = 0; i < windowsize; i++) {
if (nums[i] == 0)
count_1++;
}
// For storing maximum count of 1s in
// a window
int mx = count_1;
for (int i = windowsize; i < N + windowsize; i++) {
if (nums[i % N] == 0)
count_1++;
if (nums[(i - windowsize) % N] == 0)
count_1--;
mx = max(count_1, mx);
}
return windowsize - mx;
}
// Driver code
int main()
{
int nums[] = { 1, 0, 1, 0, 0, 1, 1 };
int N = sizeof(nums) / sizeof(nums[0]);
cout << minSwaps(nums, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to count min swap
// to get all zeros together
static int minSwaps(int nums[], int N)
{
int count_1 = 0;
if (N == 1)
return 0;
for (int i = 0; i < N; i++) {
if (nums[i] == 0)
count_1++;
}
// Window size for counting
// maximum no. of 1s
int windowsize = count_1;
count_1 = 0;
for (int i = 0; i < windowsize; i++) {
if (nums[i] == 0)
count_1++;
}
// For storing maximum count of 1s in
// a window
int mx = count_1;
for (int i = windowsize; i < N + windowsize; i++) {
if (nums[i % N] == 0)
count_1++;
if (nums[(i - windowsize) % N] == 0)
count_1--;
mx = Math.max(count_1, mx);
}
return windowsize - mx;
}
// Driver code
public static void main (String[] args) {
int nums[] = { 1, 0, 1, 0, 0, 1, 1 };
int N = nums.length;
System.out.println( minSwaps(nums, N));
}
}
// This code is contributed by hrithikgarg03188.
Python3
# python3 program for the above approach # Function to count min swap # to get all zeros together def minSwaps(nums, N): count_1 = 0 if (N == 1): return 0 for i in range(0, N): if (nums[i] == 0): count_1 += 1 # Window size for counting # maximum no. of 1s windowsize = count_1 count_1 = 0 for i in range(0, windowsize): if (nums[i] == 0): count_1 += 1 # For storing maximum count of 1s in # a window mx = count_1 for i in range(windowsize, N + windowsize): if (nums[i % N] == 0): count_1 += 1 if (nums[(i - windowsize) % N] == 0): count_1 -= 1 mx = max(count_1, mx) return windowsize - mx # Driver code if __name__ == "__main__": nums = [1, 0, 1, 0, 0, 1, 1] N = len(nums) print(minSwaps(nums, N)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
class GFG
{
// Function to count min swap
// to get all zeros together
static int minSwaps(int []nums, int N)
{
int count_1 = 0;
if (N == 1)
return 0;
for (int i = 0; i < N; i++) {
if (nums[i] == 0)
count_1++;
}
// Window size for counting
// maximum no. of 1s
int windowsize = count_1;
count_1 = 0;
for (int i = 0; i < windowsize; i++) {
if (nums[i] == 0)
count_1++;
}
// For storing maximum count of 1s in
// a window
int mx = count_1;
for (int i = windowsize; i < N + windowsize; i++) {
if (nums[i % N] == 0)
count_1++;
if (nums[(i - windowsize) % N] == 0)
count_1--;
mx = Math.Max(count_1, mx);
}
return windowsize - mx;
}
// Driver code
public static void Main()
{
int []nums = { 1, 0, 1, 0, 0, 1, 1 };
int N = nums.Length;
Console.Write(minSwaps(nums, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to count min swap
// to get all zeros together
function minSwaps(nums, N) {
let count_1 = 0;
if (N == 1)
return 0;
for (let i = 0; i < N; i++) {
if (nums[i] == 0)
count_1++;
}
// Window size for counting
// maximum no. of 1s
let windowsize = count_1;
count_1 = 0;
for (let i = 0; i < windowsize; i++) {
if (nums[i] == 0)
count_1++;
}
// For storing maximum count of 1s in
// a window
let mx = count_1;
for (let i = windowsize; i < N + windowsize; i++) {
if (nums[i % N] == 0)
count_1++;
if (nums[(i - windowsize) % N] == 0)
count_1--;
mx = Math.max(count_1, mx);
}
return windowsize - mx;
}
// Driver code
let nums = [1, 0, 1, 0, 0, 1, 1];
let N = nums.length;
document.write(minSwaps(nums, N));
// This code is contributed by Potta Lokesh
</script>
Producción
1
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por sauarbhyadav y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA