Dada una string binaria S de tamaño N , la tarea es encontrar el número mínimo de intercambios adyacentes requeridos para hacer que la string se alterne. Si no es posible hacerlo, imprima -1 .
Ejemplos:
Entrada: S = “10011”
Salida: 1
Explicación:
Intercambie el índice 2 y el índice 3 y la string se convierte en 10101.Entrada: S = “110100”
Salida: 2
Explicación:
Primero, intercambie el índice 1 y el índice 2 y la string se convierte en 101100.
En segundo lugar, intercambie el índice 3 y el índice 4 y la string se convierte en 101010.
Enfoque: para alternar la string, obtenga «1» o «0» en la primera posición. Cuando la longitud de la string es par , la string debe comenzar con «0» o «1» . Cuando la longitud de la string es impar , hay dos casos posibles: si el no. de 1 en la string es mayor que ningún 0 en la string, la string debe comenzar con » 1″ . De lo contrario, si el no. de 0 es mayor que ninguno de 1 , la string debe comenzar con «0». Por lo tanto, verifique los dos casos en los que la string binaria comienza con «1» en la primera posición y «0» en la primera posición. Siga los pasos a continuación para resolver el problema:
- Inicialice las variables unos y ceros como 0 para contar el número de ceros y unos en la string.
- Itere sobre el rango [0, N) usando la variable i y cuente el número de 0 y 1 en la string binaria.
- Compruebe los casos base, es decir, si N es par, entonces si los ceros son iguales a unos o no. Y si N es impar, entonces la diferencia entre ellos debería ser 1. Si los casos base no satisfacen, devuelve -1 .
- Inicialice la variable ans_1 como 0 para almacenar la respuesta cuando la string comience con 1 y j como 0.
- Itere sobre el rango [0, N) usando la variable i y si s[i] es igual a 1 , luego agregue el valor de abs(ji) a la variable ans_1 y aumente el valor de j en 2 .
- De manera similar, inicialice la variable ans_0 como 0 para almacenar la respuesta cuando la string comience con 1 y k como 0 .
- Itere sobre el rango [0, N) usando la variable i y si s[i] es igual a 0 , luego agregue el valor de abs(k – i) a la variable ans_0 y aumente el valor de k en 2 .
- Si N es par, imprima el mínimo de ans_1 o ans_0 como resultado. De lo contrario, si ceros es mayor que unos , imprima ans_0 . De lo contrario, imprima ans_1 .
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 find the minimum number
// of adjacent swaps to make the string
// alternating
int minSwaps(string s)
{
// Count the no of zeros and ones
int ones = 0, zeros = 0;
int N = s.length();
for (int i = 0; i < N; i++) {
if (s[i] == '1')
ones++;
else
zeros++;
}
// Base Case
if ((N % 2 == 0 && ones != zeros)
|| (N % 2 == 1
&& abs(ones - zeros) != 1)) {
return -1;
}
// Store no of min swaps when
// string starts with "1"
int ans_1 = 0;
// Keep track of the odd positions
int j = 0;
// Checking for when the string
// starts with "1"
for (int i = 0; i < N; i++) {
if (s[i] == '1') {
// Adding the no of swaps to
// fix "1" at odd positions
ans_1 += abs(j - i);
j += 2;
}
}
// Store no of min swaps when string
// starts with "0"
int ans_0 = 0;
// Keep track of the odd positions
int k = 0;
// Checking for when the string
// starts with "0"
for (int i = 0; i < N; i++) {
if (s[i] == '0') {
// Adding the no of swaps to
// fix "1" at odd positions
ans_0 += abs(k - i);
k += 2;
}
}
// Returning the answer based on
// the conditions when string
// length is even
if (N % 2 == 0)
return min(ans_1, ans_0);
// When string length is odd
else {
// When no of ones is greater
// than no of zeros
if (ones > zeros)
return ans_1;
// When no of ones is greater
// than no of zeros
else
return ans_0;
}
}
// Driver Code
int main()
{
string S = "110100";
cout << minSwaps(S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the minimum number
// of adjacent swaps to make the String
// alternating
static int minSwaps(String s)
{
// Count the no of zeros and ones
int ones = 0, zeros = 0;
int N = s.length();
for (int i = 0; i < N; i++) {
if (s.charAt(i) == '1')
ones++;
else
zeros++;
}
// Base Case
if ((N % 2 == 0 && ones != zeros)
|| (N % 2 == 1
&& Math.abs(ones - zeros) != 1)) {
return -1;
}
// Store no of min swaps when
// String starts with "1"
int ans_1 = 0;
// Keep track of the odd positions
int j = 0;
// Checking for when the String
// starts with "1"
for (int i = 0; i < N; i++) {
if (s.charAt(i) == '1') {
// Adding the no of swaps to
// fix "1" at odd positions
ans_1 += Math.abs(j - i);
j += 2;
}
}
// Store no of min swaps when String
// starts with "0"
int ans_0 = 0;
// Keep track of the odd positions
int k = 0;
// Checking for when the String
// starts with "0"
for (int i = 0; i < N; i++) {
if (s.charAt(i) == '0') {
// Adding the no of swaps to
// fix "1" at odd positions
ans_0 += Math.abs(k - i);
k += 2;
}
}
// Returning the answer based on
// the conditions when String
// length is even
if (N % 2 == 0)
return Math.min(ans_1, ans_0);
// When String length is odd
else {
// When no of ones is greater
// than no of zeros
if (ones > zeros)
return ans_1;
// When no of ones is greater
// than no of zeros
else
return ans_0;
}
}
// Driver Code
public static void main(String[] args)
{
String S = "110100";
System.out.print(minSwaps(S));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program for the above approach # Function to find the minimum number # of adjacent swaps to make the string # alternating def minSwaps(s): # Count the no of zeros and ones ones = 0 zeros = 0 N = len(s) for i in range(N): if s[i] == '1': ones += 1 else: zeros += 1 # Base Case if ((N % 2 == 0 and ones != zeros) or (N % 2 == 1 and abs(ones - zeros) != 1)): return -1 # Store no of min swaps when # string starts with "1" ans_1 = 0 # Keep track of the odd positions j = 0 # Checking for when the string # starts with "1" for i in range(N): if (s[i] == '1'): # Adding the no of swaps to # fix "1" at odd positions ans_1 += abs(j - i) j += 2 # Store no of min swaps when string # starts with "0" ans_0 = 0 # Keep track of the odd positions k = 0 # Checking for when the string # starts with "0" for i in range(N): if(s[i] == '0'): # Adding the no of swaps to # fix "1" at odd positions ans_0 += abs(k - i) k += 2 # Returning the answer based on # the conditions when string # length is even if (N % 2 == 0): return min(ans_1, ans_0) # When string length is odd else: # When no of ones is greater # than no of zeros if (ones > zeros): return ans_1 # When no of ones is greater # than no of zeros else: return ans_0 # Driver Code if __name__ == '__main__': S = "110100" print(minSwaps(S)) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum number
// of adjacent swaps to make the String
// alternating
static int minSwaps(String s)
{
// Count the no of zeros and ones
int ones = 0, zeros = 0;
int N = s.Length;
for (int i = 0; i < N; i++) {
if (s[i] == '1')
ones++;
else
zeros++;
}
// Base Case
if ((N % 2 == 0 && ones != zeros)
|| (N % 2 == 1
&& Math.Abs(ones - zeros) != 1)) {
return -1;
}
// Store no of min swaps when
// String starts with "1"
int ans_1 = 0;
// Keep track of the odd positions
int j = 0;
// Checking for when the String
// starts with "1"
for (int i = 0; i < N; i++) {
if (s[i] == '1') {
// Adding the no of swaps to
// fix "1" at odd positions
ans_1 += Math.Abs(j - i);
j += 2;
}
}
// Store no of min swaps when String
// starts with "0"
int ans_0 = 0;
// Keep track of the odd positions
int k = 0;
// Checking for when the String
// starts with "0"
for (int i = 0; i < N; i++) {
if (s[i] == '0') {
// Adding the no of swaps to
// fix "1" at odd positions
ans_0 += Math.Abs(k - i);
k += 2;
}
}
// Returning the answer based on
// the conditions when String
// length is even
if (N % 2 == 0)
return Math.Min(ans_1, ans_0);
// When String length is odd
else {
// When no of ones is greater
// than no of zeros
if (ones > zeros)
return ans_1;
// When no of ones is greater
// than no of zeros
else
return ans_0;
}
}
// Driver Code
public static void Main()
{
String S = "110100";
Console.WriteLine(minSwaps(S));
}
}
// This code is contributed by ihritik
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the minimum number
// of adjacent swaps to make the string
// alternating
function minSwaps(s)
{
// Count the no of zeros and ones
let ones = 0, zeros = 0;
let N = s.length;
for (let i = 0; i < N; i++) {
if (s.charAt(i) == '1')
ones++;
else
zeros++;
}
// Base Case
if ((N % 2 == 0 && ones != zeros)
|| (N % 2 == 1
&& Math.abs(ones - zeros) != 1)) {
return -1;
}
// Store no of min swaps when
// string starts with "1"
let ans_1 = 0;
// Keep track of the odd positions
let j = 0;
// Checking for when the string
// starts with "1"
for (let i = 0; i < N; i++) {
if (s.charAt(i) == '1') {
// Adding the no of swaps to
// fix "1" at odd positions
ans_1 += Math.abs(j - i);
j += 2;
}
}
// Store no of min swaps when string
// starts with "0"
let ans_0 = 0;
// Keep track of the odd positions
let k = 0;
// Checking for when the string
// starts with "0"
for (let i = 0; i < N; i++) {
if (s.charAt(i) == '0') {
// Adding the no of swaps to
// fix "1" at odd positions
ans_0 += Math.abs(k - i);
k += 2;
}
}
// Returning the answer based on
// the conditions when string
// length is even
if (N % 2 == 0)
return Math.min(ans_1, ans_0);
// When string length is odd
else {
// When no of ones is greater
// than no of zeros
if (ones > zeros)
return ans_1;
// When no of ones is greater
// than no of zeros
else
return ans_0;
}
}
// Driver Code
let S = "110100";
document.write(minSwaps(S));
// This code is contributed by Potta Lokesh
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por subhankarjadab y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA