Minimice el costo de intercambiar bits establecidos con bits no establecidos en una string binaria dada

Dada una string binaria S de tamaño N , la tarea es encontrar el costo mínimo intercambiando cada bit establecido con un bit no establecido de manera que el costo de intercambiar pares de bits en los índices i y j sea abs(j – i) .

Nota: un bit intercambiado no se puede intercambiar dos veces y el recuento de bits establecidos en la string binaria dada es como máximo N/2 .

Ejemplos:

Entrada: S = “1010001”
Salida: 3
Explicación:
Después del intercambio de caracteres requerido:

1. El intercambio de caracteres en los índices (0, 1) modifica la string a «0110001» y el costo de esta operación es |1 – 0| = 1.
2. El intercambio de caracteres en los índices (2, 3) modifica la string a «0101001» y el costo de esta operación es |2 – 1| = 1.
3. El intercambio de caracteres en los índices (6, 7) modifica la string a «0101010» y el costo de esta operación es |7 – 6| = 1.

Después de las operaciones anteriores, todos los bits establecidos se reemplazan con bits no establecidos y el costo total de las operaciones es 1 + 1 + 1 = 3.

Entrada: S = “1100”
Salida: 4

Enfoque: El problema dado se puede resolver utilizando Programación Dinámica almacenando los índices de bits activados y desactivados en dos arrays auxiliares , digamos A[] y B[] , y luego encuentre la suma de la diferencia entre los elementos de la array A[] con cualquier elemento de la array B[] . Siga los pasos a continuación para resolver el problema dado:

• Inicialice dos arrays , digamos A[] y B[] , y almacene en ellas los índices de bits activados y desactivados.
• Inicializar una array 2D , dp[][] de dimensiones K*(N – K) donde K es el conteo de bits establecidos en S tal que dp[i][j] almacena el costo mínimo de intercambiar el i- ^ésimo elemento A de la array [] con el j ^– ésimo elemento de array B[] .
• Ahora, para cada estado hay dos opciones:
  1. Cambie el i ^– ésimo elemento de array A[] hasta el (j – 1) ^ésimo elemento de array B[] como dp[i][j] = dp[i][j – 1] .
  2. Intercambie el (i – 1) ^ésimo elemento de array A[] hasta el (j – 1) ^ésimo elemento de array B[] y el i ^ésimo elemento de array A[] con el j ^ésimo elemento de array B[] y este estado se puede calcular como dp[i][j] = dp[i – 1][j – 1] + abs(A[i] – B[i]) .
• Ahora, elija el mínimo de las dos opciones anteriores para encontrar el estado actual como:

 dp[i][j] = min(dp[i][j-1], dp[i-1][j-1] + abs(A[i] – B[j]))

• Después de completar los pasos anteriores, imprima el valor de dp[K][N – K] como el número mínimo de operaciones resultante.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000
 
// Function to find the minimum cost
// required to swap every set bit with
// an unset bit
int minimumCost(string s)
{
    int N = s.length();
 
    // Stores the indices of set and
    // unset bits of the string S
    vector<int> A, B;
 
    // Traverse the string S
    for (int i = 0; i < N; i++) {
 
        // Store the indices
        if (s[i] == '1') {
            A.push_back(i);
        }
        else {
            B.push_back(i);
        }
    }
 
    int n1 = A.size();
    int n2 = B.size();
 
    // Initialize a dp table of size
    // n1*n2
    int dp[n1 + 1][n2 + 1];
 
    // Initialize all states to 0
    memset(dp, 0, sizeof(dp));
 
    // Set unreachable states to INF
    for (int i = 1; i <= n1; i++) {
        dp[i][0] = INF;
    }
 
    // Fill the dp Table according to
    // the given recurrence relation
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
 
            // Update the value of
            // dp[i][j]
            dp[i][j] = min(
                dp[i][j - 1],
                dp[i - 1][j - 1]
                    + abs(A[i - 1] - B[j - 1]));
        }
    }
 
    // Return the minimum cost
    return dp[n1][n2];
}
 
// Driver Code
int main()
{
    string S = "1010001";
    cout << minimumCost(S);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
static final int INF = 1000000000;
 
// Function to find the minimum cost
// required to swap every set bit with
// an unset bit
static int minimumCost(String s)
{
    int N = s.length();
 
    // Stores the indices of set and
    // unset bits of the String S
    Vector<Integer> A = new Vector<Integer>();
    Vector<Integer> B = new Vector<Integer>();
 
    // Traverse the String S
    for (int i = 0; i < N; i++) {
 
        // Store the indices
        if (s.charAt(i) == '1') {
            A.add(i);
        }
        else {
            B.add(i);
        }
    }
 
    int n1 = A.size();
    int n2 = B.size();
 
    // Initialize a dp table of size
    // n1*n2
    int [][]dp = new int[n1 + 1][n2 + 1];
 
 
    // Set unreachable states to INF
    for (int i = 1; i <= n1; i++) {
        dp[i][0] = INF;
    }
 
    // Fill the dp Table according to
    // the given recurrence relation
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
 
            // Update the value of
            // dp[i][j]
            dp[i][j] = Math.min(
                dp[i][j - 1],
                dp[i - 1][j - 1]
                    + Math.abs(A.get(i - 1) - B.get(j - 1)));
        }
    }
 
    // Return the minimum cost
    return dp[n1][n2];
}
 
// Driver Code
public static void main(String[] args)
{
    String S = "1010001";
    System.out.print(minimumCost(S));
}
}
 
// This code is contributed by shikhasingrajput

# Python program for the above approach
INF = 1000000000;
 
# Function to find the minimum cost
# required to swap every set bit with
# an unset bit
def minimumCost(s):
  N = len(s);
 
  # Stores the indices of set and
  # unset bits of the string S
  A = []
  B = []
 
  # Traverse the string S
  for i in range(0, N):
     
    # Store the indices
    if (s[i] == "1"):
      A.append(i);
    else:
      B.append(i);
     
  n1 = len(A)
  n2 = len(B)
 
  # Initialize a dp table of size
  # n1*n2
  dp = [[0 for i in range(n2 + 1)] for j in range(n1 + 1)]
 
  # Set unreachable states to INF
  for i in range(1, n1 + 1):
    dp[i][0] = INF
   
  # Fill the dp Table according to
  # the given recurrence relation
  for i in range(1, n1 + 1):
    for j in range(1, n2 + 1):
       
      # Update the value of
      # dp[i][j]
      dp[i][j] = min(
        dp[i][j - 1],
        dp[i - 1][j - 1] + abs(A[i - 1] - B[j - 1])
      );
     
  # Return the minimum cost
  return dp[n1][n2];
 
# Driver Code
S = "1010001";
print(minimumCost(S));
 
# This code is contributed by _saurabh_jaiswal.

// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
                     
public class Program
{
   
// Function to find the minimum cost
// required to swap every set bit with
// an unset bit
static int minimumCost(string s)
{
    int INF = 1000000000;
    int N = s.Length;
 
    // Stores the indices of set and
    // unset bits of the string S
    List<int> A = new List<int>();
    List<int> B = new List<int>();
 
    // Traverse the string S
    for (int i = 0; i < N; i++) {
 
        // Store the indices
        if (s[i] == '1') {
            A.Add(i);
        }
        else {
            B.Add(i);
        }
    }
 
    int n1 = A.Count;
    int n2 = B.Count;
 
    // Initialize a dp table of size
    // n1*n2
    int [,]dp = new  int[n1 + 1,n2 + 1];
 
 
    // Set unreachable states to INF
    for (int i = 1; i <= n1; i++) {
        dp[i,0] = INF;
    }
 
    // Fill the dp Table according to
    // the given recurrence relation
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
 
            // Update the value of
            // dp[i][j]
            dp[i,j] = Math.Min(
                dp[i,j - 1],
                dp[i - 1,j - 1]
                    + Math.Abs(A[i - 1] - B[j - 1]));
        }
    }
 
    // Return the minimum cost
    return dp[n1,n2];
}
     
    public static void Main()
    {
        string S = "1010001";
        Console.Write(minimumCost(S));
    }
}
 
// This code is contributed by rutvik_56.

<script>
// Javascript program for the above approach
 
let INF = 1000000000;
 
// Function to find the minimum cost
// required to swap every set bit with
// an unset bit
function minimumCost(s) {
  let N = s.length;
 
  // Stores the indices of set and
  // unset bits of the string S
  let A = [],
    B = [];
 
  // Traverse the string S
  for (let i = 0; i < N; i++) {
    // Store the indices
    if (s[i] == "1") {
      A.push(i);
    } else {
      B.push(i);
    }
  }
 
  let n1 = A.length;
  let n2 = B.length;
 
  // Initialize a dp table of size
  // n1*n2
  let dp = new Array(n1 + 1).fill(0).map(() => new Array(n2 + 1).fill(0));
 
  // Set unreachable states to INF
  for (let i = 1; i <= n1; i++) {
    dp[i][0] = INF;
  }
 
  // Fill the dp Table according to
  // the given recurrence relation
  for (let i = 1; i <= n1; i++) {
    for (let j = 1; j <= n2; j++) {
      // Update the value of
      // dp[i][j]
      dp[i][j] = Math.min(
        dp[i][j - 1],
        dp[i - 1][j - 1] + Math.abs(A[i - 1] - B[j - 1])
      );
    }
  }
 
  // Return the minimum cost
  return dp[n1][n2];
}
 
// Driver Code
 
let S = "1010001";
document.write(minimumCost(S));
 
// This code is contributed by gfgking.
</script>

3

Complejidad de tiempo: O(K*(N – K)) donde K es el conteo de bits establecidos en S .
Espacio auxiliar: O(K*(N – K))