Número de formas de cambiar el XOR de dos números intercambiando los bits

Posted on by Rudeus Greyrat

Dadas dos strings binarias s1 y s2. El XOR de ellos es X, la tarea es encontrar la cantidad de formas de intercambiar posiciones de dos bits en la string s1 de modo que el XOR formado entre el nuevo s1 y s2 no sea lo mismo que X. 

Ejemplos: 

Entrada: s1 = “01011”, s2 = “11001” 
Salida: 4 
bits de intercambio de índice (basado en 1) (1, 4), (2, 3), (3, 4) o (3, 5) como ese valor XOR se cambia. 
Entrada: s1 = “011000”, s2 = “010011” 
Salida: 6

Acercarse:  

  1. Cuente el número de 1 y 0 en s1.
  2. Atraviese la string s1 y verifique dos casos: 
    • 0 y 0 en s1[i] y s2[i], ya que reemplazar 0 con 1 cambiará el valor de XOR.
    • 1 y 0 en s1[i] y s2[i], ya que reemplazar 1 con 0 cambiará el valor de XOR.
  3. Para el primer caso, el número de formas de reemplazo será el número de unos ya usados.
  4. Para el segundo caso, el número de formas de reemplazo será el número de ceros-0’s ya usados.
  5. la suma del número de formas en ambos casos será la respuesta.

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

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function that returns the number of
// bit swaps such that xor is different
int countWays(string s1, string s2)
{
    int c1 = 0, c0 = 0;
    int n = s1.length();
 
    // traverse and count 1's and 0's
    for (int i = 0; i < n; i++) {
        if (s1[i] == '1')
            c1++;
        else
            c0++;
    }
    int used1 = 0, used0 = 0;
    int ways = 0;
 
    // traverse in the string
    for (int i = 0; i < n; i++) {
 
        // if both positions are 0
        if (s1[i] == '0' and s2[i] == '0') {
 
            // add the number of ones as
            // it will change the XOR
            ways += c1;
 
            // subtract the number of ones already used
            ways -= used1;
 
            // zeros have been used
            used0++;
        }
 
        // when 1 and 0, to change XOR, we have to
        // replace 1 by 0
        else if (s1[i] == '1' and s2[i] == '0') {
 
            // add number of 0's
            ways += c0;
 
            // subtract number of 0's already used
            ways -= used0;
 
            // count 1's used
            used1++;
        }
    }
 
    // return the answer
    return ways;
}
 
// Driver Code
int main()
{
    string s1 = "01011";
    string s2 = "11001";
 
    cout << countWays(s1, s2);
    return 0;
}

Java

// Java Program to find Number of
// ways to change the XOR of two
// numbers by swapping the bits
class GFG
{
// Function that returns the
// number of bit swaps such
// that xor is different
static int countWays(String s1,
                     String s2)
{
    int c1 = 0, c0 = 0;
    int n = s1.length();
 
    // traverse and count 1's and 0's
    for (int i = 0; i < n; i++)
    {
        if (s1.charAt(i) == '1')
            c1++;
        else
            c0++;
    }
    int used1 = 0, used0 = 0;
    int ways = 0;
 
    // traverse in the String
    for (int i = 0; i < n; i++)
    {
 
        // if both positions are 0
        if (s1.charAt(i) == '0' &&
            s2.charAt(i) == '0')
        {
 
            // add the number of ones as
            // it will change the XOR
            ways += c1;
 
            // subtract the number of
            // ones already used
            ways -= used1;
 
            // zeros have been used
            used0++;
        }
 
        // when 1 and 0, to change XOR,
        // we have to replace 1 by 0
        else if (s1.charAt(i) == '1' &&
                 s2.charAt(i) == '0')
        {
 
            // add number of 0's
            ways += c0;
 
            // subtract number of
            // 0's already used
            ways -= used0;
 
            // count 1's used
            used1++;
        }
    }
 
    // return the answer
    return ways;
}
 
// Driver Code
public static void main(String[] args)
{
    String s1 = "01011";
    String s2 = "11001";
 
    System.out.println(countWays(s1, s2));
}
}
 
// This code is contributed
// by Arnab Kundu

Python3

# Function that returns the number of
# bit swaps such that xor is different
def countWays(s1, s2):
 
    c1 = 0
    c0 = 0
    n = len(s1)
 
    # traverse and count 1's and 0's
    for i in range(0,n) :
        if (s1[i] == '1'):
            c1+=1
        else:
            c0+=1
     
    used1 = 0
    used0 = 0
    ways = 0
 
    # traverse in the string
    for i in range(0,n) :
 
        # if both positions are 0
        if (s1[i] == '0' and s2[i] == '0') :
 
            # add the number of ones as
            # it will change the XOR
            ways += c1
 
            # subtract the number of ones already used
            ways -= used1
 
            # zeros have been used
            used0+=1
         
 
        # when 1 and 0, to change XOR, we have to
        # replace 1 by 0
        elif (s1[i] == '1' and s2[i] == '0') :
 
            # add number of 0's
            ways += c0
 
            # subtract number of 0's already used
            ways -= used0
 
            # count 1's used
            used1+=1
 
    # return the answer
    return ways
 
# Driver Code
if __name__=='__main__':
    s1 = "01011"
    s2 = "11001"
    print(countWays(s1, s2))
 
# This code is contributed by Smitha Dinesh Semwal

C#

// C# Program to find Number of
// ways to change the XOR of two
// numbers by swapping the bits
using System;
 
class GFG
{
// Function that returns the
// number of bit swaps such
// that xor is different
static int countWays(String s1,
                     String s2)
{
    int c1 = 0, c0 = 0;
    int n = s1.Length;
 
    // traverse and count 1's and 0's
    for (int i = 0; i < n; i++)
    {
        if (s1[i] == '1')
            c1++;
        else
            c0++;
    }
    int used1 = 0, used0 = 0;
    int ways = 0;
 
    // traverse in the String
    for (int i = 0; i < n; i++)
    {
 
        // if both positions are 0
        if (s1[i] == '0' &&
            s2[i] == '0')
        {
 
            // add the number of ones as
            // it will change the XOR
            ways += c1;
 
            // subtract the number of
            // ones already used
            ways -= used1;
 
            // zeros have been used
            used0++;
        }
 
        // when 1 and 0, to change XOR,
        // we have to replace 1 by 0
        else if (s1[i] == '1' &&
                 s2[i] == '0')
        {
 
            // add number of 0's
            ways += c0;
 
            // subtract number of
            // 0's already used
            ways -= used0;
 
            // count 1's used
            used1++;
        }
    }
 
    // return the answer
    return ways;
}
 
// Driver Code
public static void Main(String[] args)
{
    String s1 = "01011";
    String s2 = "11001";
 
    Console.WriteLine(countWays(s1, s2));
}
}
 
// This code is contributed
// by Subhadeep Gupta

PHP

<?php
// Function that returns the 
// number of bit swaps such
// that xor is different
function countWays($s1, $s2)
{
    $c1 = 0;
    $c0 = 0;
    $n = strlen($s1);
 
    // traverse and count 1's and 0's
    for ($i = 0; $i < $n; $i++)
    {
        if ($s1[$i] == '1')
            $c1++;
        else
            $c0++;
    }
     
    $used1 = 0;
    $used0 = 0;
    $ways = 0;
     
    // traverse in the string
    for ($i = 0; $i < $n; $i++)
    {
     
        // if both positions are 0
        if ($s1[$i] == '0' and
            $s2[$i] == '0')
        {
     
            // add the number of ones as
            // it will change the XOR
            $ways += $c1;
     
            // subtract the number of
            // ones already used
            $ways -= $used1;
     
            // zeros have been used
            $used0++;
        }
     
        // when 1 and 0, to change XOR,
        // we have to replace 1 by 0
        else if ($s1[$i] == '1' and
                 $s2[$i] == '0')
        {
     
            // add number of 0's
            $ways += $c0;
     
            // subtract number of 0's
            // already used
            $ways -= $used0;
     
            // count 1's used
            $used1++;
        }
    }
     
    // return the answer
    return $ways;
}
 
// Driver Code
$s1 = "01011";
$s2 = "11001";
 
echo countWays($s1, $s2);
 
// This code is contributed
// by Shivi_Aggarwal
?>

Javascript

<script>
 
// Function that returns the number of
// bit swaps such that xor is different
function countWays(s1, s2)
{
    let c1 = 0, c0 = 0;
    let n = s1.length;
 
    // traverse and count 1's and 0's
    for (let i = 0; i < n; i++) {
        if (s1[i] == '1')
            c1++;
        else
            c0++;
    }
    let used1 = 0, used0 = 0;
    let ways = 0;
 
    // traverse in the string
    for (let i = 0; i < n; i++) {
 
        // if both positions are 0
        if (s1[i] == '0' && s2[i] == '0') {
 
            // add the number of ones as
            // it will change the XOR
            ways += c1;
 
            // subtract the number of ones already used
            ways -= used1;
 
            // zeros have been used
            used0++;
        }
 
        // when 1 and 0, to change XOR, we have to
        // replace 1 by 0
        else if (s1[i] == '1' && s2[i] == '0') {
 
            // add number of 0's
            ways += c0;
 
            // subtract number of 0's already used
            ways -= used0;
 
            // count 1's used
            used1++;
        }
    }
 
    // return the answer
    return ways;
}
 
// Driver Code
    let s1 = "01011";
    let s2 = "11001";
 
    document.write(countWays(s1, s2));
 
</script>

Producción:  

4

Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *