Intercambios mínimos requeridos para hacer una string binaria alterna

Se le da una string binaria de longitud par y el mismo número de 0 y 1. ¿Cuál es el número mínimo de intercambios para que la string se alterne? Una string binaria es alterna si no hay dos elementos consecutivos iguales.

Ejemplos: 

Input : 000111
Output : 1
Explanation : Swap index 2 and index 5 to get 010101

Input : 1010
Output : 0 

Podemos obtener un 1 en la primera posición o un cero en la primera posición. Consideramos dos casos y encontramos el mínimo de dos casos. Tenga en cuenta que se da que hay números iguales de 1 y 0 en la string y la string tiene una longitud uniforme.
1. Cuente el número de ceros en la posición impar y en la posición par de la string. Deje que su cuenta sea impar_0 y par_0 respectivamente. 
2. Cuente el número de unos en la posición impar y en la posición par de la cuerda. Deje que su cuenta sea impar_1 y par_1 respectivamente. 
3. Siempre intercambiaremos un 1 con un 0 (nunca un 1 con un 1 o un 0 con un 0). Entonces, solo verificamos si nuestra string alterna comienza con 0, entonces el número de intercambios es mínimo (par_0, impar_1) y si nuestra string alterna comienza con 1, entonces el número de intercambios es mínimo (par_1, impar_0). La respuesta es min de estos dos.

A continuación se muestra la implementación del enfoque anterior:

C++

// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
    // returns the minimum number of swaps
    // of a binary string
    // passed as the argument
    // to make it alternating
    int countMinSwaps(string st)
    {
 
        int min_swaps = 0;
 
        // counts number of zeroes at odd
        // and even positions
        int odd_0 = 0, even_0 = 0;
 
        // counts number of ones at odd
        // and even positions
        int odd_1 = 0, even_1 = 0;
 
        int n = st.length();
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                if (st[i] == '1')
                    even_1++;
                else
                    even_0++;
            }
            else {
                if (st[i] == '1')
                    odd_1++;
                else
                    odd_0++;
            }
        }
 
        // alternating string starts with 0
        int cnt_swaps_1 = min(even_0, odd_1);
 
        // alternating string starts with 1
        int cnt_swaps_2 = min(even_1, odd_0);
 
        // calculates the minimum number of swaps
        return min(cnt_swaps_1, cnt_swaps_2);
    }
 
    // Driver code
    int main()
    {
        string st = "000111";
        cout<<countMinSwaps(st)<<endl;
 
         return 0;
    }
 
// This code is contributed by Surendra_Gangwar

Java

// Java implementation of the approach
 
class GFG {
 
    // returns the minimum number of swaps
    // of a binary string
    // passed as the argument
    // to make it alternating
    static int countMinSwaps(String st)
    {
 
        int min_swaps = 0;
 
        // counts number of zeroes at odd
        // and even positions
        int odd_0 = 0, even_0 = 0;
 
        // counts number of ones at odd
        // and even positions
        int odd_1 = 0, even_1 = 0;
 
        int n = st.length();
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                if (st.charAt(i) == '1')
                    even_1++;
                else
                    even_0++;
            }
            else {
                if (st.charAt(i) == '1')
                    odd_1++;
                else
                    odd_0++;
            }
        }
 
        // alternating string starts with 0
        int cnt_swaps_1 = Math.min(even_0, odd_1);
 
        // alternating string starts with 1
        int cnt_swaps_2 = Math.min(even_1, odd_0);
 
        // calculates the minimum number of swaps
        return Math.min(cnt_swaps_1, cnt_swaps_2);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String st = "000111";
        System.out.println(countMinSwaps(st));
    }
}

Python3

# Python3 implementation of the
# above approach
 
# returns the minimum number of swaps
# of a binary string
# passed as the argument
# to make it alternating
def countMinSwaps(st) :
 
    min_swaps = 0
 
    # counts number of zeroes at odd
    # and even positions
    odd_0, even_0 = 0, 0
 
    # counts number of ones at odd
    # and even positions
    odd_1, even_1 = 0, 0
 
    n = len(st)
 
    for i in range(0, n) :
 
        if i % 2 == 0 :
 
            if st[i] == "1" :
                even_1 += 1
            else :
                even_0 += 1
                 
        else :
            if st[i] == "1" :
                odd_1 += 1
            else :
                odd_0 += 1
 
    # alternating string starts with 0
    cnt_swaps_1 = min(even_0, odd_1)
 
    # alternating string starts with 1
    cnt_swaps_2 = min(even_1, odd_0)
 
    # calculates the minimum number of swaps
    return min(cnt_swaps_1, cnt_swaps_2)
 
# Driver code    
if __name__ == "__main__" :
 
    st = "000111"
 
    # Function call
    print(countMinSwaps(st))
 
# This code is contributed by
# ANKITRAI1

C#

// C# implementation of the approach
using System;
 
public class GFG
{
 
    // returns the minimum number of swaps
    // of a binary string
    // passed as the argument
    // to make it alternating
    public static int countMinSwaps(string st)
    {
 
        int min_swaps = 0;
 
        // counts number of zeroes at odd 
        // and even positions
        int odd_0 = 0, even_0 = 0;
 
        // counts number of ones at odd 
        // and even positions
        int odd_1 = 0, even_1 = 0;
 
        int n = st.Length;
        for (int i = 0; i < n; i++)
        {
            if (i % 2 == 0)
            {
                if (st[i] == '1')
                {
                    even_1++;
                }
                else
                {
                    even_0++;
                }
            }
            else
            {
                if (st[i] == '1')
                {
                    odd_1++;
                }
                else
                {
                    odd_0++;
                }
            }
        }
 
        // alternating string starts with 0
        int cnt_swaps_1 = Math.Min(even_0, odd_1);
 
        // alternating string starts with 1
        int cnt_swaps_2 = Math.Min(even_1, odd_0);
 
        // calculates the minimum number of swaps
        return Math.Min(cnt_swaps_1, cnt_swaps_2);
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        string st = "000111";
        Console.WriteLine(countMinSwaps(st));
    }
}
 
// This code is contributed by Shrikant13

PHP

<?php
// PHP implementation of the approach
// returns the minimum number of swaps
// of a binary string passed as the
// argument to make it alternating
function countMinSwaps($st)
{
    $min_swaps = 0;
 
    // counts number of zeroes at odd
    // and even positions
    $odd_0 = 0;
    $even_0 = 0;
 
    // counts number of ones at odd
    // and even positions
    $odd_1 = 0;
    $even_1 = 0;
 
    $n = strlen($st);
    for ($i = 0; $i < $n; $i++)
    {
        if ($i % 2 == 0)
        {
            if ($st[$i] == '1')
            {
                $even_1++;
            }
            else
            {
                $even_0++;
            }
        }
        else
        {
            if ($st[$i] == '1')
            {
                $odd_1++;
            }
            else
            {
                $odd_0++;
            }
        }
    }
 
    // alternating string starts with 0
    $cnt_swaps_1 = min($even_0, $odd_1);
 
    // alternating string starts with 1
    $cnt_swaps_2 = min($even_1, $odd_0);
 
    // calculates the minimum number of swaps
    return min($cnt_swaps_1, $cnt_swaps_2);
}
 
// Driver code
$st = "000111";
echo (countMinSwaps($st));
 
// This code is contributed by Sachin.
?>

Javascript

<script>
    // Javascript implementation of the approach
     
    // returns the minimum number of swaps
    // of a binary string
    // passed as the argument
    // to make it alternating
    function countMinSwaps(st)
    {
  
        let min_swaps = 0;
  
        // counts number of zeroes at odd
        // and even positions
        let odd_0 = 0, even_0 = 0;
  
        // counts number of ones at odd
        // and even positions
        let odd_1 = 0, even_1 = 0;
  
        let n = st.length;
        for (let i = 0; i < n; i++)
        {
            if (i % 2 == 0)
            {
                if (st[i] == '1')
                {
                    even_1++;
                }
                else
                {
                    even_0++;
                }
            }
            else
            {
                if (st[i] == '1')
                {
                    odd_1++;
                }
                else
                {
                    odd_0++;
                }
            }
        }
  
        // alternating string starts with 0
        let cnt_swaps_1 = Math.min(even_0, odd_1);
  
        // alternating string starts with 1
        let cnt_swaps_2 = Math.min(even_1, odd_0);
  
        // calculates the minimum number of swaps
        return Math.min(cnt_swaps_1, cnt_swaps_2);
    }
     
    let st = "000111";
      document.write(countMinSwaps(st));
     
    // This code is contributed by divyesh072019.
</script>
Producción: 

1

 

Enfoque para strings de longitud par e impar:

Deje que la longitud de la string sea N.

En este enfoque, consideraremos tres casos:
1. La respuesta es imposible cuando el número total de unos > el número total de ceros + 1 o el número total de ceros > el número total de unos + 1.
2. La string tiene una longitud par 
    : cuente el número de unos en posiciones impares (one_odd) y el número de unos en posiciones pares (one_even), luego la respuesta es min (N/2 – one_odd, N/2 – one_even) 
3. La string tiene una longitud impar:
    Aquí consideramos dos casos :
     i) número total de unos > número total de ceros (entonces hemos puesto unos en posiciones pares) entonces, la respuesta es ((N + 1) / 2 – número de unos en posiciones pares).
    ii) número total de ceros > número total de unos (entonces hemos puesto ceros en posiciones pares) entonces, la respuesta es ((N + 1) / 2 – número de ceros en posiciones pares). 

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// function to count minimum swaps
// required to make binary string
// alternating
int countMinSwaps(string s)
{
    int N = s.size();
 
    // stores total number of ones
    int one = 0;
 
    // stores total number of zeroes
    int zero = 0;
 
    for (int i = 0; i < N; i++) {
        if (s[i] == '1')
            one++;
        else
            zero++;
    }
 
    // checking impossible condition
    if (one > zero + 1 || zero > one + 1)
        return -1;
 
    // odd length string
    if (N % 2) {
        // number of even positions
        int num = (N + 1) / 2;
 
        // stores number of zeroes and
        // ones at even positions
        int one_even = 0, zero_even = 0;
 
        for (int i = 0; i < N; i++) {
            if (i % 2 == 0) {
                if (s[i] == '1')
                    one_even++;
                else
                    zero_even++;
            }
        }
 
        if (one > zero)
            return num - one_even;
 
        else
            return num - zero_even;
    }
 
    // even length string
    else {
        // stores number of ones at odd
        // and even position respectively
        int one_odd = 0, one_even = 0;
 
        for (int i = 0; i < N; i++) {
            if (s[i] == '1') {
                if (i % 2)
                    one_odd++;
 
                else
                    one_even++;
            }
        }
 
        return min(N / 2 - one_odd, N / 2 - one_even);
    }
}
 
// Driver code
int main()
{
    string s = "111000";
 
    cout << countMinSwaps(s);
 
    return 0;
}

Java

// Java implementation of the above approach
import java.util.*;
 
class GFG{
 
// function to count minimum swaps
// required to make binary String
// alternating
static int countMinSwaps(String s)
{
    int N = s.length();
 
    // stores total number of ones
    int one = 0;
 
    // stores total number of zeroes
    int zero = 0;
 
    for (int i = 0; i < N; i++) {
        if (s.charAt(i) == '1')
            one++;
        else
            zero++;
    }
 
    // checking impossible condition
    if (one > zero + 1 || zero > one + 1)
        return -1;
 
    // odd length String
    if (N % 2 == 1)
    {
       
        // number of even positions
        int num = (N + 1) / 2;
 
        // stores number of zeroes and
        // ones at even positions
        int one_even = 0, zero_even = 0;
 
        for (int i = 0; i < N; i++) {
            if (i % 2 == 0) {
                if (s.charAt(i) == '1')
                    one_even++;
                else
                    zero_even++;
            }
        }
 
        if (one > zero)
            return num - one_even;
 
        else
            return num - zero_even;
    }
 
    // even length String
    else
    {
       
        // stores number of ones at odd
        // and even position respectively
        int one_odd = 0, one_even = 0;
 
        for (int i = 0; i < N; i++) {
            if (s.charAt(i) == '1') {
                if (i % 2 == 1)
                    one_odd++;
 
                else
                    one_even++;
            }
        }
 
        return Math.min(N / 2 - one_odd, N / 2 - one_even);
    }
}
 
// Driver code
public static void main(String[] args)
{
    String s = "111000";
 
    System.out.print(countMinSwaps(s));
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python implementation of the above approach
# function to count minimum swaps
# required to make binary string
# alternating
def countMinSwaps(s):
    N = len(s)
 
    # stores total number of ones
    one = 0
 
    # stores total number of zeroes
    zero = 0
 
    for i in range(N):
        if (s[i] == '1'):
            one += 1
        else:
            zero += 1
     
    # checking impossible condition
    if (one > zero + 1 or zero > one + 1):
        return -1
 
    # odd length string
    if (N % 2):
       
        # number of even positions
        num = (N + 1) / 2
 
        # stores number of zeroes and
        # ones at even positions
        one_even = 0
        zero_even = 0
 
        for i in range(N):
            if (i % 2 == 0):
                if (s[i] == '1'):
                    one_even+=1
                else:
                    zero_even+=1
             
        if (one > zero):
            return num - one_even
 
        else:
            return num - zero_even
     
    # even length string
    else:
        # stores number of ones at odd
        # and even position respectively
        one_odd = 0
        one_even = 0
 
        for i in range(N):
            if (s[i] == '1'):
                if (i % 2):
                    one_odd+=1
 
                else:
                    one_even+=1
             
        return min(N // 2 - one_odd, N // 2 - one_even)
 
# Driver code
s = "111000"
print(countMinSwaps(s))
 
# This code is contributed by shivanisinghss2110

C#

// C# implementation of the above approach
using System;
 
class GFG{
 
// Function to count minimum swaps
// required to make binary String
// alternating
static int countMinSwaps(string s)
{
    int N = s.Length;
 
    // Stores total number of ones
    int one = 0;
 
    // Stores total number of zeroes
    int zero = 0;
 
    for(int i = 0; i < N; i++)
    {
        if (s[i] == '1')
            one++;
        else
            zero++;
    }
 
    // Checking impossible condition
    if (one > zero + 1 || zero > one + 1)
        return -1;
 
    // Odd length String
    if (N % 2 == 1)
    {
       
        // Number of even positions
        int num = (N + 1) / 2;
 
        // Stores number of zeroes and
        // ones at even positions
        int one_even = 0, zero_even = 0;
 
        for(int i = 0; i < N; i++)
        {
            if (i % 2 == 0)
            {
                if (s[i] == '1')
                    one_even++;
                else
                    zero_even++;
            }
        }
        if (one > zero)
            return num - one_even;
        else
            return num - zero_even;
    }
 
    // Even length String
    else
    {
         
        // Stores number of ones at odd
        // and even position respectively
        int one_odd = 0, one_even = 0;
 
        for(int i = 0; i < N; i++)
        {
            if (s[i] == '1')
            {
                if (i % 2 == 1)
                    one_odd++;
                else
                    one_even++;
            }
        }
        return Math.Min(N / 2 - one_odd,
                        N / 2 - one_even);
    }
}
 
// Driver code
public static void Main(String[] args)
{
    string s = "111000";
 
    Console.Write(countMinSwaps(s));
}
}
 
// This code is contributed by shivanisinghss2110

Javascript

<script>
// JavaScript implementation of the above approach
// function to count minimum swaps
// required to make binary String
// alternating
function countMinSwaps(s)
{
    var N = s.length;
 
    // stores total number of ones
    var one = 0;
 
    // stores total number of zeroes
    var zero = 0;
 
    for (var i = 0; i < N; i++) {
        if (s.charAt(i) == '1')
            one++;
        else
            zero++;
    }
 
    // checking impossible condition
    if (one > zero + 1 || zero > one + 1)
        return -1;
 
    // odd length String
    if (N % 2 == 1)
    {
       
        // number of even positions
        var num = (N + 1) / 2;
 
        // stores number of zeroes and
        // ones at even positions
        var one_even = 0, zero_even = 0;
 
        for (var i = 0; i < N; i++) {
            if (i % 2 == 0) {
                if (s.charAt(i) == '1')
                    one_even++;
                else
                    zero_even++;
            }
        }
 
        if (one > zero)
            return num - one_even;
 
        else
            return num - zero_even;
    }
 
    // even length String
    else
    {
       
        // stores number of ones at odd
        // and even position respectively
        var one_odd = 0, one_even = 0;
 
        for (var i = 0; i < N; i++) {
            if (s.charAt(i) == '1') {
                if (i % 2 == 1)
                    one_odd++;
 
                else
                    one_even++;
            }
        }
 
        return Math.min(N / 2 - one_odd, N / 2 - one_even);
    }
}
 
// Driver code
var s = "111000";
 
document.write(countMinSwaps(s));
 
// This code is contributed by shivanisinghss2110
 
</script>
Producción

1

Complejidad de tiempo: O (longitud de string)

Publicación traducida automáticamente

Artículo escrito por AmanKumarSingh 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 *