Intercambios mínimos requeridos para agrupar todos los 1 juntos

Dada una array de 0 y 1, necesitamos escribir un programa para encontrar el número mínimo de intercambios necesarios para agrupar todos los 1 presentes en la array.

Ejemplos: 

Input : arr[] = {1, 0, 1, 0, 1}
Output : 1
Explanation: Only 1 swap is required to 
group all 1's together. Swapping index 1
and 4 will give arr[] = {1, 1, 1, 0, 0}

Input : arr[] = {1, 0, 1, 0, 1, 1}
Output : 1

Una solución simple es primero contar el número total de 1 en la array. Supongamos que este conteo es x, ahora necesitamos encontrar el subarreglo de longitud x de este arreglo con el número máximo de 1. Y los intercambios mínimos requeridos serán el número de 0 en el subarreglo de longitud x con el número máximo de 1. 
Complejidad temporal: O(n 2 )

Una solución eficiente es optimizar la técnica de fuerza bruta para encontrar el subarreglo en el enfoque anterior utilizando el concepto de técnica de ventana deslizante . Podemos mantener un arreglo preCount para encontrar el número de 1 presentes en un subarreglo en una complejidad de tiempo O(1).

A continuación se muestra la implementación de la idea anterior: 

C++

// C++ program to find minimum swaps
// required to group all 1's together
#include <iostream>
#include <limits.h>
 
using namespace std;
 
// Function to find minimum swaps
// to group all 1's together
int minSwaps(int arr[], int n) {
 
  int noOfOnes = 0;
 
  // find total number of all in the array
  for (int i = 0; i < n; i++) {
    if (arr[i] == 1)
      noOfOnes++;
  }
 
  // length of subarray to check for
  int x = noOfOnes;
 
  int maxOnes = INT_MIN;
 
  // array to store number of 1's upto
  // ith index
  int preCompute[n] = {0};
 
  // calculate number of 1's upto ith
  // index and store in the array preCompute[]
  if (arr[0] == 1)
    preCompute[0] = 1;
  for (int i = 1; i < n; i++) {
    if (arr[i] == 1) {
      preCompute[i] = preCompute[i - 1] + 1;
    } else
      preCompute[i] = preCompute[i - 1];
  }
 
  // using sliding window technique to find
  // max number of ones in subarray of length x
  for (int i = x - 1; i < n; i++) {
    if (i == (x - 1))
      noOfOnes = preCompute[i];
    else
      noOfOnes = preCompute[i] - preCompute[i - x];
     
    if (maxOnes < noOfOnes)
      maxOnes = noOfOnes;
  }
 
  // calculate number of zeros in subarray
  // of length x with maximum number of 1's
  int noOfZeroes = x - maxOnes;
 
  return noOfZeroes;
}
 
// Driver Code
int main() {
  int a[] = {1, 0, 1, 0, 1};
  int n = sizeof(a) / sizeof(a[0]);
  cout << minSwaps(a, n);
  return 0;
}

Java

// Java  program to find minimum swaps
// required to group all 1's together
 
import java.io.*;
 
class GFG {
 
// Function to find minimum swaps
// to group all 1's together
 static int minSwaps(int arr[], int n) {
 
int noOfOnes = 0;
 
// find total number of all in the array
for (int i = 0; i < n; i++) {
    if (arr[i] == 1)
    noOfOnes++;
}
 
// length of subarray to check for
int x = noOfOnes;
 
int maxOnes = Integer.MIN_VALUE;
 
// array to store number of 1's upto
// ith index
int preCompute[] = new int[n];
 
// calculate number of 1's upto ith
// index and store in the array preCompute[]
if (arr[0] == 1)
    preCompute[0] = 1;
for (int i = 1; i < n; i++) {
    if (arr[i] == 1) {
    preCompute[i] = preCompute[i - 1] + 1;
    } else
    preCompute[i] = preCompute[i - 1];
}
 
// using sliding window technique to find
// max number of ones in subarray of length x
for (int i = x - 1; i < n; i++) {
    if (i == (x - 1))
    noOfOnes = preCompute[i];
    else
    noOfOnes = preCompute[i] - preCompute[i - x];
     
    if (maxOnes < noOfOnes)
    maxOnes = noOfOnes;
}
 
// calculate number of zeros in subarray
// of length x with maximum number of 1's
int noOfZeroes = x - maxOnes;
 
return noOfZeroes;
}
 
// Driver Code
public static void main (String[] args) {
int a[] = {1, 0, 1, 0, 1};
int n = a.length;
System.out.println( minSwaps(a, n));
     
    }
}
 
// This code is contributed by vt_m.

Python3

# Python program to
# find minimum swaps
# required to group
# all 1's together
 
# Function to find minimum swaps
# to group all 1's together
def minSwaps(arr,n):
     
    noOfOnes = 0
  
    # find total number of
    # all in the array
    for i in range(n):
        if (arr[i] == 1):
            noOfOnes=noOfOnes+1
   
  
    # length of subarray to check for
    x = noOfOnes
  
    maxOnes = -2147483648
  
    # array to store number of 1's upto
    # ith index
    preCompute={}
  
    # calculate number of 1's upto ith
    # index and store in the
    # array preCompute[]
    if (arr[0] == 1):
        preCompute[0] = 1
    for i in range(1,n):
        if (arr[i] == 1):
            preCompute[i] = preCompute[i - 1] + 1
        else:
            preCompute[i] = preCompute[i - 1]
   
  
    # using sliding window
    # technique to find
    # max number of ones in
    # subarray of length x
    for i in range(x-1,n):
        if (i == (x - 1)):
            noOfOnes = preCompute[i]
        else:
            noOfOnes = preCompute[i] - preCompute[i - x]
      
        if (maxOnes < noOfOnes):
            maxOnes = noOfOnes
   
  
    # calculate number of zeros in subarray
    # of length x with maximum number of 1's
    noOfZeroes = x - maxOnes
  
    return noOfZeroes
   
# Driver code
 
a = [1, 0, 1, 0, 1]
n = len(a)
 
print(minSwaps(a, n))
 
# This code is contributed
# by Anant Agarwal.

C#

// C# program to find minimum swaps
// required to group all 1's together
 
using System;
 
class GFG {
 
    // Function to find minimum swaps
    // to group all 1's together
    static int minSwaps(int []arr, int n) {
     
        int noOfOnes = 0;
         
        // find total number of all in the array
        for (int i = 0; i < n; i++) {
            if (arr[i] == 1)
            noOfOnes++;
        }
         
        // length of subarray to check for
        int x = noOfOnes;
         
        int maxOnes = int.MinValue;
         
        // array to store number of 1's upto
        // ith index
        int []preCompute = new int[n];
         
        // calculate number of 1's upto ith
        // index and store in the array preCompute[]
        if (arr[0] == 1)
            preCompute[0] = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] == 1) {
            preCompute[i] = preCompute[i - 1] + 1;
            } else
            preCompute[i] = preCompute[i - 1];
        }
         
        // using sliding window technique to find
        // max number of ones in subarray of length x
        for (int i = x - 1; i < n; i++) {
            if (i == (x - 1))
            noOfOnes = preCompute[i];
            else
            noOfOnes = preCompute[i] - preCompute[i - x];
             
            if (maxOnes < noOfOnes)
            maxOnes = noOfOnes;
        }
         
        // calculate number of zeros in subarray
        // of length x with maximum number of 1's
        int noOfZeroes = x - maxOnes;
         
        return noOfZeroes;
    }
     
    // Driver Code
    public static void Main ()
    {
        int []a = {1, 0, 1, 0, 1};
        int n = a.Length;
        Console.WriteLine( minSwaps(a, n));
         
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to find minimum swaps
// required to group all 1's together
 
// Function to find minimum swaps
// to group all 1's together
function minSwaps($arr, $n)
{
 
        $noOfOnes = 0;
         
        // find total number of
        // all in the array
        for($i = 0; $i < $n; $i++)
        {
            if ($arr[$i] == 1)
            $noOfOnes++;
        }
         
        // length of subarray
        // to check for
        $x = $noOfOnes;
         
        $maxOnes = PHP_INT_MIN;
         
        // array to store number of
        // 1's upto ith index
        $preCompute = array();
         
        // calculate number of 1's
        // upto ith index and store
        // in the array preCompute[]
        if ($arr[0] == 1)
            $preCompute[0] = 1;
        for($i = 1; $i < $n; $i++)
        {
            if ($arr[$i] == 1)
            {
                $preCompute[$i] = $preCompute[$i - 1] + 1;
            }
            else
                $preCompute[$i] = $preCompute[$i - 1];
        }
         
        // using sliding window
        // technique to find
        // max number of ones in
        // subarray of length x
        for ( $i = $x - 1; $i < $n; $i++)
        {
            if ($i == ($x - 1))
                $noOfOnes = $preCompute[$i];
            else
                $noOfOnes = $preCompute[$i] -
                            $preCompute[$i - $x];
             
            if ($maxOnes < $noOfOnes)
                $maxOnes = $noOfOnes;
        }
         
        // calculate number of zeros in subarray
        // of length x with maximum number of 1's
        $noOfZeroes = $x - $maxOnes;
         
        return $noOfZeroes;
}
 
// Driver Code
$a = array(1, 0, 1, 0, 10);
$n = count($a);
echo minSwaps($a, $n);
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
    // Javascript program to find minimum swaps
    // required to group all 1's together
     
    // Function to find minimum swaps
    // to group all 1's together
    function minSwaps(arr, n) {
      
        let noOfOnes = 0;
          
        // find total number of all in the array
        for (let i = 0; i < n; i++) {
            if (arr[i] == 1)
                noOfOnes++;
        }
          
        // length of subarray to check for
        let x = noOfOnes;
          
        let maxOnes = Number.MIN_VALUE;
          
        // array to store number of 1's upto
        // ith index
        let preCompute = new Array(n);
        preCompute.fill(0);
          
        // calculate number of 1's upto ith
        // index and store in the array preCompute[]
        if (arr[0] == 1)
            preCompute[0] = 1;
        for (let i = 1; i < n; i++) {
            if (arr[i] == 1) {
                preCompute[i] = preCompute[i - 1] + 1;
            } else
                preCompute[i] = preCompute[i - 1];
        }
          
        // using sliding window technique to find
        // max number of ones in subarray of length x
        for (let i = x - 1; i < n; i++) {
            if (i == (x - 1))
                noOfOnes = preCompute[i];
            else
                noOfOnes = preCompute[i] - preCompute[i - x];
              
            if (maxOnes < noOfOnes)
                maxOnes = noOfOnes;
        }
          
        // calculate number of zeros in subarray
        // of length x with maximum number of 1's
        let noOfZeroes = x - maxOnes;
          
        return noOfZeroes;
    }
     
    let a = [1, 0, 1, 0, 1];
    let n = a.length;
    document.write( minSwaps(a, n));
         
</script>
Producción

1

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(n)

Otro enfoque eficiente: 
primero cuente el número total de 1 en la array. Suponga que este conteo es x, ahora encuentre el subarreglo de longitud x de este arreglo con el número máximo de 1 usando el concepto de técnica de deslizamiento de ventanas . Mantenga una variable para encontrar el número de 1 presentes en un subarreglo en O (1) espacio adicional y para cada subarreglo mantenga la variable maxOnes y, por último, devuelva el número de ceros (número de ceros = x – maxOnes).

C++

// C++ code for minimum swaps
// required to group all 1's together
#include <iostream>
#include <limits.h>
 
using namespace std;
 
// Function to find minimum swaps
// to group all 1's together
int minSwaps(int arr[], int n)
{
 
int numberOfOnes = 0;
 
// find total number of all 1's in the array
for (int i = 0; i < n; i++) {
    if (arr[i] == 1)
    numberOfOnes++;
}
 
// length of subarray to check for
int x = numberOfOnes;
 
int count_ones = 0, maxOnes;
 
// Find 1's for first subarray of length x
for(int i = 0; i < x; i++){
    if(arr[i] == 1)
    count_ones++;
}
     
maxOnes = count_ones;
     
// using sliding window technique to find
// max number of ones in subarray of length x
for (int i = 1; i <= n-x; i++) {
     
    // first remove leading element and check
    // if it is equal to 1 then decrement the
    // value of count_ones by 1
    if (arr[i-1] == 1)
    count_ones--;
     
    // Now add trailing element and check
    // if it is equal to 1 Then increment
    // the value of count_ones by 1
    if(arr[i+x-1] == 1)
    count_ones++;
     
    if (maxOnes < count_ones)
    maxOnes = count_ones;
}
 
// calculate number of zeros in subarray
// of length x with maximum number of 1's
int numberOfZeroes = x - maxOnes;
 
return numberOfZeroes;
}
 
// Driver Code
int main() {
     
int a[] = {0, 0, 1, 0, 1, 1, 0, 0, 1};
int n = sizeof(a) / sizeof(a[0]);
 
cout << minSwaps(a, n);
 
return 0;
 
}

Java

// java program to find largest number
// smaller than equal to n with m set
// bits then m-1 0 bits.
public class GFG {
     
    // Function to find minimum swaps
    // to group all 1's together
    static int minSwaps(int arr[], int n)
    {
     
        int numberOfOnes = 0;
         
        // find total number of all 1's
        // in the array
        for (int i = 0; i < n; i++) {
            if (arr[i] == 1)
                numberOfOnes++;
        }
         
        // length of subarray to check for
        int x = numberOfOnes;
         
        int count_ones = 0, maxOnes;
         
        // Find 1's for first subarray
        // of length x
        for(int i = 0; i < x; i++){
            if(arr[i] == 1)
                count_ones++;
        }
             
        maxOnes = count_ones;
             
        // using sliding window technique
        // to find max number of ones in
        // subarray of length x
        for (int i = 1; i <= n-x; i++) {
             
            // first remove leading element
            // and check if it is equal to
            // 1 then decrement the
            // value of count_ones by 1
            if (arr[i - 1] == 1)
                count_ones--;
             
            // Now add trailing element
            // and check if it is equal
            // to 1 Then increment the
            // value of count_ones by 1
            if(arr[i + x - 1] == 1)
                count_ones++;
             
            if (maxOnes < count_ones)
            maxOnes = count_ones;
        }
         
        // calculate number of zeros in
        // subarray of length x with
        // maximum number of 1's
        int numberOfZeroes = x - maxOnes;
         
        return numberOfZeroes;
    }
     
    // Driver code
    public static void main(String args[])
    {
        int a[] = new int[]{0, 0, 1, 0,
                            1, 1, 0, 0, 1};
        int n = a.length;
         
        System.out.println(minSwaps(a, n));
    }
}
 
// This code is contributed by Sam007

Python3

# Python code for minimum
# swaps required to group
# all 1's together
 
# Function to find minimum
# swaps to group all 1's
# together
def minSwaps(arr, n) :
 
    numberOfOnes = 0
     
    # find total number of
    # all 1's in the array
    for i in range(0, n) :
 
        if (arr[i] == 1) :
            numberOfOnes = numberOfOnes + 1
     
    # length of subarray
    # to check for
    x = numberOfOnes
     
    count_ones = 0
    maxOnes = 0
     
    # Find 1's for first
    # subarray of length x
    for i in range(0, x) :
 
        if(arr[i] == 1) :
            count_ones = count_ones + 1
         
    maxOnes = count_ones
         
    # using sliding window
    # technique to find
    # max number of ones in
    # subarray of length x
    for i in range(1, (n - x + 1)) :
         
        # first remove leading
        # element and check
        # if it is equal to 1
        # then decrement the
        # value of count_ones by 1
        if (arr[i - 1] == 1) :
            count_ones = count_ones - 1
         
        # Now add trailing
        # element and check
        # if it is equal to 1
        # Then increment
        # the value of count_ones by 1
        if(arr[i + x - 1] == 1) :
            count_ones = count_ones + 1
         
        if (maxOnes < count_ones) :
                maxOnes = count_ones
     
    # calculate number of
    # zeros in subarray
    # of length x with
    # maximum number of 1's
    numberOfZeroes = x - maxOnes
     
    return numberOfZeroes
 
# Driver Code
a = [0, 0, 1, 0, 1, 1, 0, 0, 1]
n = 9
print (minSwaps(a, n))
 
# This code is contributed
# by Manish Shaw(manishshaw1)

C#

// C# code for minimum swaps
// required to group all 1's together
using System;
 
class GFG{
     
    // Function to find minimum swaps
    // to group all 1's together
    static int minSwaps(int []arr, int n)
    {
     
        int numberOfOnes = 0;
         
        // find total number of all 1's in the array
        for (int i = 0; i < n; i++) {
            if (arr[i] == 1)
            numberOfOnes++;
        }
         
        // length of subarray to check for
        int x = numberOfOnes;
         
        int count_ones = 0, maxOnes;
         
        // Find 1's for first subarray of length x
        for(int i = 0; i < x; i++){
            if(arr[i] == 1)
            count_ones++;
        }
             
        maxOnes = count_ones;
             
        // using sliding window technique to find
        // max number of ones in subarray of length x
        for (int i = 1; i <= n-x; i++) {
             
            // first remove leading element and check
            // if it is equal to 1 then decrement the
            // value of count_ones by 1
            if (arr[i - 1] == 1)
            count_ones--;
             
            // Now add trailing element and check
            // if it is equal to 1 Then increment
            // the value of count_ones by 1
            if(arr[i + x - 1] == 1)
            count_ones++;
             
            if (maxOnes < count_ones)
            maxOnes = count_ones;
        }
         
        // calculate number of zeros in subarray
        // of length x with maximum number of 1's
        int numberOfZeroes = x - maxOnes;
         
        return numberOfZeroes;
    }
     
    // Driver Code
    static public void Main ()
    {
        int []a = {0, 0, 1, 0, 1, 1, 0, 0, 1};
        int n = a.Length;
     
        Console.WriteLine(minSwaps(a, n));
         
    }
}
// This code is contributed by vt_m.

PHP

<?php
// PHP code for minimum swaps
// required to group all 1's together
 
// Function to find minimum swaps
// to group all 1's together
function minSwaps($arr, $n)
{
 
    $numberOfOnes = 0;
     
    // find total number of
    // all 1's in the array
    for ($i = 0; $i < $n; $i++)
    {
        if ($arr[$i] == 1)
            $numberOfOnes++;
    }
     
    // length of subarray to check for
    $x = $numberOfOnes;
     
    $count_ones = 0;
    $maxOnes;
     
    // Find 1's for first
    // subarray of length x
    for($i = 0; $i < $x; $i++)
    {
        if($arr[$i] == 1)
            $count_ones++;
    }
         
    $maxOnes = $count_ones;
         
    // using sliding window
    // technique to find
    // max number of ones in
    // subarray of length x
    for ($i = 1; $i <= $n - $x; $i++)
    {
         
        // first remove leading
        // element and check
        // if it is equal to 1
        // then decrement the
        // value of count_ones by 1
        if ($arr[$i - 1] === 1)
            $count_ones--;
         
        // Now add trailing
        // element and check
        // if it is equal to 1
        // Then increment
        // the value of count_ones by 1
        if($arr[$i + $x - 1] === 1)
                $count_ones++;
         
        if ($maxOnes < $count_ones)
                $maxOnes = $count_ones;
    }
     
    // calculate number of zeros in subarray
    // of length x with maximum number of 1's
    $numberOfZeroes = $x - $maxOnes;
     
    return $numberOfZeroes;
}
 
// Driver Code
$a = array(0, 0, 1, 0, 1, 1, 0, 0, 1);
$n = 9;
echo minSwaps($a, $n);
 
// This code is contributed by Anuj_67
?>

Javascript

<script>   
    // Javascript code for minimum swaps
    // required to group all 1's together
     
    // Function to find minimum swaps
    // to group all 1's together
    function minSwaps(arr, n)
    {
      
        let numberOfOnes = 0;
          
        // find total number of all 1's in the array
        for (let i = 0; i < n; i++) {
            if (arr[i] == 1)
            numberOfOnes++;
        }
          
        // length of subarray to check for
        let x = numberOfOnes;
          
        let count_ones = 0, maxOnes;
          
        // Find 1's for first subarray of length x
        for(let i = 0; i < x; i++){
            if(arr[i] == 1)
            count_ones++;
        }
              
        maxOnes = count_ones;
              
        // using sliding window technique to find
        // max number of ones in subarray of length x
        for (let i = 1; i <= n-x; i++) {
              
            // first remove leading element and check
            // if it is equal to 1 then decrement the
            // value of count_ones by 1
            if (arr[i - 1] == 1)
                count_ones--;
              
            // Now add trailing element and check
            // if it is equal to 1 Then increment
            // the value of count_ones by 1
            if(arr[i + x - 1] == 1)
                count_ones++;
              
            if (maxOnes < count_ones)
                maxOnes = count_ones;
        }
          
        // calculate number of zeros in subarray
        // of length x with maximum number of 1's
        let numberOfZeroes = x - maxOnes;
          
        return numberOfZeroes;
    }
     
    let a = [0, 0, 1, 0, 1, 1, 0, 0, 1];
    let n = a.length;
 
    document.write(minSwaps(a, n));
 
</script>
Producción

1

Complejidad de tiempo: O(n) 
Espacio auxiliar: O(1)
Gracias al Sr. Gera por sugerir este enfoque.

Ventana corredera Versión fácil de entender

Algoritmo:

1. Almacene el número total de unos en una variable digamos contar. Este será el tamaño de la ventana.

2. Inicialice una variable para almacenar el número máximo de unos de todos los subconjuntos de conteo de tamaño y una variable para almacenar el conteo de unos en la ventana actual.

3. Ahora itere sobre la array y, tan pronto como alcance el tamaño de la ventana, compare el número de unos en esa ventana con el número máximo de unidades en todas las ventanas hasta el momento y actualice el número máximo de unidades si el número de unidades en la ventana actual es más. Si el primer elemento de la ventana es 1, disminuya el recuento actual.

4. La respuesta será el conteo total de unos – el conteo máximo de unos de todas las ventanas.

C++

#include <bits/stdc++.h>
 
using namespace std;
 
int minSwaps(int arr[], int n)
{
  int totalCount = 0; // To store total number of ones
  // count total no of ones
  for (int i = 0; i < n; i++)
    totalCount += arr[i];
 
  int currCount = 0; // To store count of ones in current window
  int maxCount = 0;  // To store maximum count ones out of all windows
  int i = 0;         // start of window
  int j = 0;         // end of window
 
  while (j < n)
  {
    currCount += arr[j];
 
    // update maxCount when reach window size i.e. total count of ones in array
    if ((j - i + 1) == totalCount)
    {
      maxCount = max(maxCount, currCount);
      if (arr[i] == 1)
        currCount--; // decrease current count if first element of window is 1
      i++;           // slide window
    }
    j++;
  }
 
  return totalCount - maxCount; // return total no of ones in array - maximum count of ones out of all windows
}
 
// Driver Code
int main()
{
 
  int a[] = {1, 0, 1, 0, 1, 1};
  int n = sizeof(a) / sizeof(a[0]);
 
  cout << minSwaps(a, n);
 
  return 0;
}

Java

import java.io.*;
import java.util.*;
 
class GFG{
     
static int minSwaps(int[] arr, int n)
{
     
    // To store total number of ones
    int totalCount = 0;
     
    // Count total no of ones
    int i;
    for(i = 0; i < n; i++)
        totalCount += arr[i];
 
    int currCount = 0; // To store count of ones in current window
    int maxCount = 0;  // To store maximum count ones out
                       // of all windows
                       
    // start of window
    i = 0;
     
    // end of window
    int j = 0;
 
    while (j < n)
    {
        currCount += arr[j];
 
        // update maxCount when reach window size i.e.
        // total count of ones in array
        if ((j - i + 1) == totalCount)
        {
            maxCount = Math.max(maxCount, currCount);
            if (arr[i] == 1)
                currCount--; // decrease current count
                             // if first element of
                             // window is 1
                              
            // slide window
            i++;
        }
        j++;
    }
 
    return totalCount - maxCount; // return total no of ones in array
                                  // - maximum count of ones out of
                                  // all windows
}
 
// Driver Code
public static void main(String args[])
    {
    int[] a = { 1, 0, 1, 0, 1, 1 };
    int n = a.length;
 
    System.out.println(minSwaps(a, n));
}
}
 
// This code is contributed by shivanisinghss2110

Python

def minSwaps(arr, n):
   
    # To store total number of ones
    totalCount = 0
     
    # count total no of ones
    for i in range(0,n):
        totalCount += arr[i]
         
    currCount = 0 # To store count of ones in current window
    maxCount = 0  # To store maximum count ones out of all windows
    i = 0         # start of window
    j = 0         # end of window
     
    while (j < n):
        currCount += arr[j]
         
        # update maxCount when reach window size i.e. total count of ones in array
        if ((j - i + 1) == totalCount):
            maxCount = max(maxCount, currCount)
            if (arr[i] == 1):
                currCount -= 1
                 
                # decrease current count if first element of window is 1
            i += 1           # slide window
        j += 1
     
    return totalCount - maxCount # return total no of ones in array - maximum count of ones out of all windows
 
# Driver Code
a = [1, 0, 1, 0, 1, 1]
n = len(a)
print(minSwaps(a, n))
 
# this code is contributed by shivanisighss2110

C#

using System;
 
class GFG{
     
static int minSwaps(int[] arr, int n)
{
     
    // To store total number of ones
    int totalCount = 0;
     
    // Count total no of ones
    int i;
    for(i = 0; i < n; i++)
        totalCount += arr[i];
 
    int currCount = 0; // To store count of ones in current window
    int maxCount = 0;  // To store maximum count ones out
                       // of all windows
                       
    // start of window
    i = 0;
     
    // end of window
    int j = 0;
 
    while (j < n)
    {
        currCount += arr[j];
 
        // update maxCount when reach window size i.e.
        // total count of ones in array
        if ((j - i + 1) == totalCount)
        {
            maxCount = Math.Max(maxCount, currCount);
            if (arr[i] == 1)
                currCount--; // decrease current count
                             // if first element of
                             // window is 1
                              
            // slide window
            i++;
        }
        j++;
    }
 
    return totalCount - maxCount; // return total no of ones in array
                                  // - maximum count of ones out of
                                  // all windows
}
 
// Driver Code
public static void Main()
{
    int[] a = { 1, 0, 1, 0, 1, 1 };
    int n = a.Length;
 
    Console.WriteLine(minSwaps(a, n));
}
}
 
// This code is contributed by ukasp

Javascript

<script>
 
function minSwaps(arr, n)
{
     
    // To store total number of ones
    let totalCount = 0;
     
    // Count total no of ones
    let i;
    for(i = 0; i < n; i++)
        totalCount += arr[i];
 
    let currCount = 0; // To store count of ones in current window
    let maxCount = 0;  // To store maximum count ones out
                       // of all windows
                       
    // start of window
    i = 0;
     
    // end of window
    let j = 0;
 
    while (j < n)
    {
        currCount += arr[j];
 
        // update maxCount when reach window size i.e.
        // total count of ones in array
        if ((j - i + 1) == totalCount)
        {
            maxCount = Math.max(maxCount, currCount);
            if (arr[i] == 1)
                currCount--; // decrease current count
                             // if first element of
                             // window is 1
                              
            // slide window
            i++;
        }
        j++;
    }
 
    return totalCount - maxCount; // return total no of ones in array
                                  // - maximum count of ones out of
                                  // all windows
}
 
// Driver Code
 
    let a = [ 1, 0, 1, 0, 1, 1 ];
    let n = a.length;
 
    document.write(minSwaps(a, n));
     
// This code is contributed by shivanisinghss2110
 
</script>
Producción

1

Complejidades: 

Tiempo en)

Espacio: O(1)

Publicación traducida automáticamente

Artículo escrito por harsh.agarwal0 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *