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>
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>
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