Número mínimo de operaciones necesarias para maximizar la string binaria

Dada una string binaria S , la tarea es encontrar el número mínimo de intercambios necesarios para maximizar el valor representado por S .

Ejemplos:

Entrada: S = “1010001” 
Salida: 1 
Explicación: Al intercambiar S[2] y S[7], se modifica la string a 1110000 y, por lo tanto, se maximiza el número que se puede generar a partir de la string.
Entrada: S = “110001001” 
Salida: 2 
Explicación: Intercambiando S[3] con S[6] y S[4] con S[9], obtenemos 111100000 que es la string requerida

Enfoque ingenuo: 
se puede observar que, para maximizar la string requerida, los caracteres deben intercambiarse de manera que todos los 0 estén a la derecha y todos los 1 estén a la izquierda. Por lo tanto, la string debe modificarse a una secuencia » 1…10…0 «.

Siga los pasos a continuación para resolver el problema:

1. Cuente el número de 1 s en la string S , digamos cnt1 .
2. Cuente el número de 0 s en la substring S[0], …, S[cnt1-1] , digamos cnt0 .
3. Imprima cnt0 como la respuesta requerida.

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number
// of operations required
int minOperation(string s, int n)
{
 
    // Count of 1's
    int cnt1 = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1')
            cnt1++;
    }
 
    // Count of 0's upto (cnt1)-th index
    int cnt0 = 0;
    for (int i = 0; i < cnt1; i++) {
        if (s[i] == '0')
            cnt0++;
    }
 
    // Return the answer
    return cnt0;
}
 
// Driver Code
int main()
{
    int n = 8;
 
    string s = "01001011";
 
    int ans = minOperation(s, n);
 
    cout << ans << endl;
}

// Java program to implement
// the above approach
class GFG{
 
// Function to find the number
// of operations required
static int minOperation(String s, int n)
{
     
    // Count of 1's
    int cnt1 = 0;
    for(int i = 0; i < n; i++)
    {
        if (s.charAt(i) == '1')
            cnt1++;
    }
 
    // Count of 0's upto (cnt1)-th index
    int cnt0 = 0;
    for(int i = 0; i < cnt1; i++)
    {
        if (s.charAt(i) == '0')
            cnt0++;
    }
 
    // Return the answer
    return cnt0;
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 8;
 
    String s = "01001011";
 
    int ans = minOperation(s, n);
 
    System.out.print(ans + "\n");
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program to implement
# the above approach
 
# Function to find the number
# of operations required
def minOperation(s, n):
     
    # Count of 1's
    cnt1 = 0;
     
    for i in range(n):
        if (ord(s[i]) == ord('1')):
            cnt1 += 1;
 
    # Count of 0's upto (cnt1)-th index
    cnt0 = 0;
     
    for i in range(0, cnt1):
        if (s[i] == '0'):
            cnt0 += 1;
 
    # Return the answer
    return cnt0;
 
# Driver Code
if __name__ == '__main__':
     
    n = 8;
    s = "01001011";
    ans = minOperation(s, n);
 
    print(ans);
 
# This code is contributed by Amit Katiyar

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to find the number
// of operations required
static int minOperation(String s, int n)
{
     
    // Count of 1's
    int cnt1 = 0;
    for(int i = 0; i < n; i++)
    {
        if (s[i] == '1')
            cnt1++;
    }
 
    // Count of 0's upto (cnt1)-th index
    int cnt0 = 0;
    for(int i = 0; i < cnt1; i++)
    {
        if (s[i] == '0')
            cnt0++;
    }
 
    // Return the answer
    return cnt0;
}
 
// Driver Code
public static void Main(String[] args)
{
    int n = 8;
 
    String s = "01001011";
 
    int ans = minOperation(s, n);
 
    Console.Write(ans + "\n");
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// JavaScript Program to implement
// the above approach
 
// Function to find the number
// of operations required
function minOperation(s,n)
{
 
    // Count of 1's
    let cnt1 = 0;
    for (let i = 0; i < n; i++) {
        if (s[i] == '1')
            cnt1++;
    }
 
    // Count of 0's upto (cnt1)-th index
    let cnt0 = 0;
    for (let i = 0; i < cnt1; i++) {
        if (s[i] == '0')
            cnt0++;
    }
 
    // Return the answer
    return cnt0;
}
 
// Driver Code
let n = 8;
let s = "01001011";
let ans = minOperation(s, n);
document.write(ans,"</br>");
 
// This code is contributed by shinjanpatra
 
</script>

3

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)

Enfoque eficiente: 
 

El enfoque anterior se puede optimizar aún más utilizando la técnica Two Pointers . Siga los pasos a continuación para resolver el problema:

• Establezca dos punteros i = 0 y j = S.length() – 1 e itere hasta que i exceda j .
• Aumente la cuenta , si S[i] es igual a ‘ 0 ‘ y S[j] es igual a ‘ 1 ‘.
• Incremente i si S[i] es ‘ 1 ‘ hasta que aparezca un ‘ 0 ‘. De manera similar, disminuya j hasta que S[j] sea igual a ‘ 1 ‘.
• Imprima el conteo como la respuesta requerida.

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number
// of operations required
int minOperation(string s, int n)
{
 
    int ans = 0;
    int i = 0, j = n - 1;
    while (i < j) {
 
        // Swap 0's and 1's
        if (s[i] == '0' && s[j] == '1') {
            ans++;
            i++;
            j--;
            continue;
        }
 
        if (s[i] == '1') {
            i++;
        }
 
        if (s[j] == '0') {
            j--;
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
    int n = 8;
 
    string s = "10100101";
 
    int ans = minOperation(s, n);
 
    cout << ans << endl;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to find the number
// of operations required
static int minOperation(String s, int n)
{
    int ans = 0;
    int i = 0, j = n - 1;
     
    while (i < j)
    {
         
        // Swap 0's and 1's
        if (s.charAt(i) == '0' &&
            s.charAt(j) == '1')
        {
            ans++;
            i++;
            j--;
            continue;
        }
 
        if (s.charAt(i) == '1')
        {
            i++;
        }
 
        if (s.charAt(j) == '0')
        {
            j--;
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver code
public static void main (String[] args)
{
    int n = 8;
     
    String s = "10100101";
     
    System.out.println(minOperation(s, n));
}
}
 
// This code is contributed by offbeat

# Python3 program to implement
# the above approach
 
# Function to find the number
# of operations required
def minOperation(s, n):
    ans = 0;
    i = 0; j = n - 1;
 
    while (i < j):
 
        # Swap 0's and 1's
        if (s[i] == '0' and s[j] == '1'):
            ans += 1;
            i += 1;
            j -= 1;
            continue;
         
        if (s[i] == '1'):
            i += 1;
         
        if (s[j] == '0'):
            j -= 1;
         
    # Return the answer
    return ans;
 
# Driver code
if __name__ == '__main__':
    n = 8;
 
    s = "10100101";
 
    print(minOperation(s, n));
 
# This code is contributed by sapnasingh4991

// C# program to implement
// the above approach
using System;
class GFG{
 
// Function to find the number
// of operations required
static int minOperation(String s, int n)
{
    int ans = 0;
    int i = 0, j = n - 1;
     
    while (i < j)
    {
         
        // Swap 0's and 1's
        if (s[i] == '0' &&
            s[j] == '1')
        {
            ans++;
            i++;
            j--;
            continue;
        }
 
        if (s[i] == '1')
        {
            i++;
        }
 
        if (s[j] == '0')
        {
            j--;
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 8;
     
    String s = "10100101";
     
    Console.WriteLine(minOperation(s, n));
}
}
 
// This code is contributed by sapnasingh4991

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to find the number
// of operations required
function minOperation(s, n)
{
    let ans = 0;
    let i = 0, j = n - 1;
      
    while (i < j)
    {
          
        // Swap 0's and 1's
        if (s[i] == '0' &&
            s[j] == '1')
        {
            ans++;
            i++;
            j--;
            continue;
        }
  
        if (s[i]== '1')
        {
            i++;
        }
  
        if (s[j] == '0')
        {
            j--;
        }
    }
  
    // Return the answer
    return ans;
}
 
// Driver Code
 
    let n = 8;
      
    let s = "10100101";
      
    document.write(minOperation(s, n));
 
</script>

Producción:  

2

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)