Convierta la string binaria dada a otra en operaciones mínimas al voltear todos los bits excepto cualquier 1

Dadas dos strings binarias s1 y s2 , la tarea es contar las operaciones mínimas para convertir la string s1 a s2 . En una operación, se puede elegir un bit establecido y todos los demás bits, excepto el que se invierte. Si no es posible convertir s1-> s2 print -1 .

Ejemplos: 

Entrada: s1 = “100010111” s2 = “101101100”
Salida: 3
Explicación: 
En la primera operación, mantenga 1 en el sexto índice y convierta el resto en NOT lógico: 100010 1 11→011101100.
En la segunda operación, mantenga 1 en el primer índice y convierta el resto en NOT lógico: 0 1 1101100→110010011.
En la tercera operación, mantenga 1 en el índice 0 y convierta el resto en NOT lógico: 1 10010011→101101100.
Así que 3 operaciones.

Entrada: s1=”11111″ s2 = “00000”
Salida: -1

Enfoque: se puede ver eligiendo el mismo índice de 1 después de dos operaciones, la string sigue siendo la misma que la original. Por lo tanto, se debe elegir un índice diferente para cada operación al hacerlo, «10» en la string s1 se puede convertir en una string «01» en la string s2 con dos operaciones. Entonces, la respuesta depende de minimizar el número de «10» y «01» en las strings s1 y s2. Si en cualquier índice “0(s1) – 1(s2) “ && “1(s1) – 0(s2)”  son iguales en número, entonces hay una respuesta más -1.

“01” (al elegir 1 en el índice 1) -> “11” (al elegir 1 en el índice 2) -> “10”

Usando esta conclusión: 
Incluso puede ser posible que los pares mínimos “0(s1) – 1(s2) ” && “1(s1) – 0(s2)” puedan obtenerse realizando 1 operación inicialmente. En los casos en que 1 (s1)-> 1(s2) o 1(s1) -> 0(s2).

Siga estos pasos para resolver este problema:

• Inicializar la variable res = INT_MAX
• Inicialice la variable ops1= -1 para almacenar las operaciones requeridas para convertir la string s1 a s2 sin ninguna modificación.
• Ahora compruebe si es posible minimizar las operaciones haciendo 1 modificación inicial en el caso de (1(s1)-> 1(s2)) .
• Almacene las operaciones en la variable ops2 y almacene el mínimo en res haciendo min(res,ops2) .
• Ahora compruebe si es posible minimizar las operaciones haciendo 1 modificación inicial en el caso de (1(s1)-> 0(s2)) .
• Almacene las operaciones en la variable ops3 y almacene el mínimo en res haciendo min(res,ops3) .
• Si res es igual a INT_MAX , significa que no es posible convertir la string s1 -> s2, así que imprima -1.
• De lo contrario, imprima el res .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the "0(s1)-1(s2)"
// && "1(s1)- 0(s2)" pairs
int count_operations(string s1, string s2)
{
    int n = s1.size();
     
    // Initializing to 0 initially
    int cnt10 = 0, cnt01 = 0;
    for (int i = 0; i < n; i++) {
        if (s1[i] != s2[i]) {
            if (s1[i] == '0')
                cnt01++;
            else
                cnt10++;
        }
    }
     
    // Equal 0(s1)-1(s2) and 1(s1)- 0(s2) pairs
    // To convert 1 pair 2 operations are required
    // so 2 * cnt01
    if (cnt01 == cnt10)
        return 2 * cnt01;
    return -1;
}
 
// Function to do one operation of
// modifying the string s1
bool modify_string(string& s1, string& s2,
                   char c)
{
    int n = s1.size();
    int idx = -1;
     
    // Find the index of occurrence of
    // 1(s1)- c(s2) in s1
    for (int i = 0; i < n; i++) {
        if (s1[i] == '1' && s2[i] == c) {
             
            // Break if found
            idx = i;
            break;
        }
    }
    if (idx == -1)
        return 0;
     
    // Flip the remaining except that index
    for (int i = 0; i < n; i++) {
        if (i == idx)
            continue;
        if (s1[i] == '1')
            s1[i] = '0';
        else
            s1[i] = '1';
    }
    return 1;
}
 
// Function to find the minimum operations
// to convert the string s1 to string s2
int find_min_operations(string s1, string s2)
{
    int res = INT_MAX;
     
    // Case -1 Initial strings itself
    int ops1 = count_operations(s1, s2);
   
    if (ops1 != -1)
        res = min(res, ops1);
 
    string a = s1, b = s2;
     
    // Case -2 Doing 1 modification initially
    // for 1(s1)-1(s2)
    if (modify_string(a, b, '1')) {
   
        int ops2 = count_operations(a, b);
         
        // Take minimum
        if (ops2 != -1)
            res = min(res, 1 + ops2);
        
    }
  
 
    // Case-3 doing 1 modification initially
    // for 1(s1) - 0(s2)
    a = s1, b = s2;
    if (modify_string(a, b, '0')) {
        int ops3 = count_operations(a, b);
         
        // Take minimum
        if (ops3 != -1)
            res = min(res, 1 + ops3);
    }
 
    if (res == INT_MAX)
        return -1;
    else
        return res;
}
 
// Driver code
int main()
{
    string s1 = "100010111";
    string s2 = "101101100";
     
    // Function call
    cout << find_min_operations(s1, s2) << endl;
    return 0;
}

# Python program for the above approach
INT_MAX = 2147483647;
 
# Function to count the "0(s1)-1(s2)"
# && "1(s1)- 0(s2)" pairs
def count_operations (s1, s2):
    n = len(s1);
 
    # Initializing to 0 initially
    cnt10 = 0
    cnt01 = 0;
    for i in range(n):
        if (s1[i] != s2[i]):
            if (s1[i] == '0'):
                cnt01 += 1
            else:
                cnt10 += 1
 
    # Equal 0(s1)-1(s2) and 1(s1)- 0(s2) pairs
    # To convert 1 pair 2 operations are required
    # so 2 * cnt01
    if (cnt01 == cnt10):
        return 2 * cnt01;
    return -1;
 
# Function to do one operation of
# modifying the let s1
def modify_string (s1, s2, c):
    n = len(s1);
    idx = -1;
 
    # Find the index of occurrence of
    # 1(s1)- c(s2) in s1
    for i in range(n):
        if (s1[i] == '1' and s2[i] == c):
 
            # Break if found
            idx = i;
            break;
    if (idx == -1):
        return 0;
 
    # Flip the remaining except that index
    for i in range(n):
        if (i == idx):
            continue;
        if (s1[i] == '1'):
            s1[i] = '0';
        else:
            s1[i] = '1';
    return 1;
 
 
# Function to find the minimum operations
# to convert the let s1 to let s2
def find_min_operations (s1, s2):
    res = 10 ** 9;
 
    # Case -1 Initial strings itself
    ops1 = count_operations(s1, s2);
    if (ops1 != -1):
        res = min(res, ops1);
 
    a = s1
    b = s2;
    # Case -2 Doing 1 modification initially
    # for 1(s1)-1(s2)
    if (modify_string(a, b, '1')):
        ops2 = count_operations(a, b);
 
        # Take minimum
        if (ops2 != -1):
            res = min(res, 1 + ops2);
 
    # Case-3 doing 1 modification initially
    # for 1(s1) - 0(s2)
    a = s1
    b = s2;
    if (modify_string(a, b, '0')):
        ops3 = count_operations(a, b);
 
        # Take minimum
        if (ops3 != -1):
            res = min(res, 1 + ops3);
 
    if (res == 10 ** 9):
        return -1;
    else:
        return res;
 
 
# Driver code
s1 = "100010111";
s2 = "101101100";
s1 = list(s1);
s2 = list(s2);
 
# Function call
print(find_min_operations(s1, s2));
 
# This code is contributed by gfgking

// C# program for the above approach
using System;
class GFG {
 
  // Function to count the "0(s1)-1(s2)"
  // && "1(s1)- 0(s2)" pairs
  static int count_operations(string s1, string s2)
  {
    int n = s1.Length;
 
    // Initializing to 0 initially
    int cnt10 = 0, cnt01 = 0;
    for (int i = 0; i < n; i++) {
      if (s1[i] != s2[i]) {
        if (s1[i] == '0')
          cnt01++;
        else
          cnt10++;
      }
    }
 
    // Equal 0(s1)-1(s2) and 1(s1)- 0(s2) pairs
    // To convert 1 pair 2 operations are required
    // so 2 * cnt01
    if (cnt01 == cnt10)
      return 2 * cnt01;
    return -1;
  }
 
  // Function to do one operation of
  // modifying the string s1
  static int modify_string(ref string s1, ref string s2,
                           char c)
  {
    int n = s1.Length;
    char[] str1 = s1.ToCharArray();
    char[] str2 = s2.ToCharArray();
 
    int idx = -1;
 
    // Find the index of occurrence of
    // 1(s1)- c(s2) in s1
    for (int i = 0; i < n; i++) {
      if (str1[i] == '1' && str2[i] == c) {
 
        // Break if found
        idx = i;
        break;
      }
    }
    if (idx == -1)
      return 0;
 
    // Flip the remaining except that index
    for (int i = 0; i < n; i++) {
      if (i == idx)
        continue;
      if (str1[i] == '1')
        str1[i] = '0';
      else
        str1[i] = '1';
    }
    s1 = new string(str1);
    s2 = new string(str2);
    return 1;
  }
 
  // Function to find the minimum operations
  // to convert the string s1 to string s2
  static int find_min_operations(string s1, string s2)
  {
    int res = Int32.MaxValue;
 
    // Case -1 Initial strings itself
    int ops1 = count_operations(s1, s2);
 
    if (ops1 != -1)
      res = Math.Min(res, ops1);
 
    string a = s1, b = s2;
 
    // Case -2 Doing 1 modification initially
    // for 1(s1)-1(s2)
    if (modify_string(ref a, ref b, '1') > 0) {
      int ops2 = count_operations(a, b);
 
      // Take minimum
      if (ops2 != -1)
        res = Math.Min(res, 1 + ops2);
    }
 
    // Case-3 doing 1 modification initially
    // for 1(s1) - 0(s2)
    a = s1;
    b = s2;
    if (modify_string(ref a, ref b, '0') > 0) {
      int ops3 = count_operations(a, b);
 
      // Take minimum
      if (ops3 != -1)
        res = Math.Min(res, 1 + ops3);
    }
 
    if (res == Int32.MaxValue)
      return -1;
    else
      return res;
  }
 
  // Driver code
  public static void Main()
  {
    string s1 = "100010111";
    string s2 = "101101100";
 
    // Function call
    Console.WriteLine(find_min_operations(s1, s2));
  }
}
 
// This code is contributed by ukasp.

<script>
    // JavaScript program for the above approach
    const INT_MAX = 2147483647;
 
    // Function to count the "0(s1)-1(s2)"
    // && "1(s1)- 0(s2)" pairs
    const count_operations = (s1, s2) => {
        let n = s1.length;
 
        // Initializing to 0 initially
        let cnt10 = 0, cnt01 = 0;
        for (let i = 0; i < n; i++) {
            if (s1[i] !== s2[i]) {
                if (s1[i] === '0')
                    cnt01++;
                else
                    cnt10++;
            }
        }
 
        // Equal 0(s1)-1(s2) and 1(s1)- 0(s2) pairs
        // To convert 1 pair 2 operations are required
        // so 2 * cnt01
        if (cnt01 === cnt10)
            return 2 * cnt01;
        return -1;
    }
 
    // Function to do one operation of
    // modifying the let s1
    const modify_string = (s1, s2, c) => {
        let n = s1.length;
        let idx = -1;
 
        // Find the index of occurrence of
        // 1(s1)- c(s2) in s1
        for (let i = 0; i < n; i++) {
            if (s1[i] === '1' && s2[i] === c) {
 
                // Break if found
                idx = i;
                break;
            }
        }
        if (idx === -1)
            return 0;
 
        // Flip the remaining except that index
        for (let i = 0; i < n; i++) {
            if (i === idx)
                continue;
            if (s1[i] == '1')
                s1[i] = '0';
            else
                s1[i] = '1';
        }
        return 1;
    }
 
    // Function to find the minimum operations
    // to convert the let s1 to let s2
    const find_min_operations = (s1, s2) => {
        let res = INT_MAX;
 
        // Case -1 Initial strings itself
        let ops1 = count_operations(s1, s2);
        if (ops1 !== -1)
            res = Math.min(res, ops1);
 
        let a = s1, b = s2;
        // Case -2 Doing 1 modification initially
        // for 1(s1)-1(s2)
        if (modify_string(a, b, '1')) {
            let ops2 = count_operations(a, b);
 
            // Take minimum
            if (ops2 !== -1)
                res = Math.min(res, 1 + ops2);
        }
 
        // Case-3 doing 1 modification initially
        // for 1(s1) - 0(s2)
        a = s1, b = s2;
        if (modify_string(a, b, '0')) {
            let ops3 = count_operations(a, b);
 
            // Take minimum
            if (ops3 !== -1)
                res = Math.min(res, 1 + ops3);
        }
 
        if (res === INT_MAX)
            return -1;
        else
            return res;
    }
 
    // Driver code
    let s1 = "100010111";
    let s2 = "101101100";
    s1 = s1.split('');
    s2 = s2.split('');
     
    // Function call
    document.write(find_min_operations(s1, s2));
 
    // This code is contributed by rakeshsahni
 
</script>

// Java program for the above approach
import java.util.*;
public class GFG {
 
  // Function to count the "0(s1)-1(s2)"
  // && "1(s1)- 0(s2)" pairs
  static int count_operations(String s1, String s2)
  {
    int n = s1.length();
 
    // Initializing to 0 initially
    int cnt10 = 0, cnt01 = 0;
    for (int i = 0; i < n; i++) {
      if (s1.charAt(i) != s2.charAt(i)) {
        if (s1.charAt(i) == '0')
          cnt01++;
        else
          cnt10++;
      }
    }
 
    // Equal 0(s1)-1(s2) and 1(s1)- 0(s2) pairs
    // To convert 1 pair 2 operations are required
    // so 2 * cnt01
    if (cnt01 == cnt10)
      return 2 * cnt01;
    return -1;
  }
 
  // Function to do one operation of
  // modifying the string s1
  static int modify_string(String s1, String s2,
                           char c)
  {
    int n = s1.length();
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
 
    int idx = -1;
 
    // Find the index of occurrence of
    // 1(s1)- c(s2) in s1
    for (int i = 0; i < n; i++) {
      if (str1[i] == '1' && str2[i] == c) {
 
        // Break if found
        idx = i;
        break;
      }
    }
    if (idx == -1)
      return 0;
 
    // Flip the remaining except that index
    for (int i = 0; i < n; i++) {
      if (i == idx)
        continue;
      if (str1[i] == '1')
        str1[i] = '0';
      else
        str1[i] = '1';
    }
    s1 = new String(str1);
    s2 = new String(str2);
    return 1;
  }
 
  // Function to find the minimum operations
  // to convert the string s1 to string s2
  static int find_min_operations(String s1, String s2)
  {
    int res = Integer.MAX_VALUE;
 
    // Case -1 Initial strings itself
    int ops1 = count_operations(s1, s2);
    ops1 /= 2;
     
    if (ops1 != -1)
      res = Math.min(res, ops1);
 
    String a = s1, b = s2;
 
    // Case -2 Doing 1 modification initially
    // for 1(s1)-1(s2)
    if (modify_string(a, b, '1') > 0) {
      int ops2 = count_operations(a, b);
 
      // Take minimum
      if (ops2 != -1)
        res = Math.min(res, 1 + ops2);
    }
 
    // Case-3 doing 1 modification initially
    // for 1(s1) - 0(s2)
    a = s1;
    b = s2;
    if (modify_string(a, b, '0') > 0) {
      int ops3 = count_operations(a, b);
 
      // Take minimum
      if (ops3 != -1)
        res = Math.min(res, 1 + ops3);
    }
 
    if (res == Integer.MAX_VALUE)
      return -1;
    else
      return res;
  }
 
  // Driver code
  public static void main(String args[])
  {
    String s1 = "100010111";
    String s2 = "101101100";
 
    // Function call
    System.out.println(find_min_operations(s1, s2));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

3

Complejidad de tiempo: O(N) donde N es la longitud de la string.
Complejidad espacial: O(N)