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