Dada una secuencia de tres secuencias binarias A, B y C de N bits. Cuente los bits mínimos necesarios para voltear A y B de modo que XOR de A y B sea igual a C. Por ejemplo:
Input: N = 3
A = 110
B = 101
C = 001
Output: 1
We only need to flip the bit of 2nd position
of either A or B, such that A ^ B = C i.e.,
100 ^ 101 = 001
Un enfoque ingenuo es generar todas las combinaciones posibles de bits en A y B y luego XOR para verificar si es igual a C o no. La complejidad temporal de este enfoque crece exponencialmente, por lo que no sería mejor para un gran valor de N.
Otro enfoque es usar el concepto de XOR.
XOR Truth Table Input Output X Y Z 0 0 - 0 0 1 - 1 1 0 - 1 1 1 - 0
Si generalizamos, encontraremos que en cualquier posición de A y B, solo necesitamos cambiar la i -ésima posición (0 a N-1) de A o B; de lo contrario, no podremos alcanzar el número mínimo de Bits.
Entonces, en cualquier posición de i (0 a N-1) encontrará dos tipos de situaciones, es decir, A[i] == B[i] o A[i] != B[i]. Discutámoslo uno por uno.
- Si A[i] == B[i] entonces el XOR de estos bits será 0, se dan dos casos en C[]: C[i]==0 o C[i]==1.
Si C[i] == 0, entonces no es necesario voltear el bit, pero si C[i] == 1, entonces tenemos que voltear el bit en A[i] o B[i] para que 1^0 == 1 o 0^1 == 1.
- Si A[i] != B[i] entonces XOR de estos bits da un 1, en C surgen de nuevo dos casos, es decir, C[i] == 0 o C[i] == 1.
Por lo tanto, si C[i ] == 1, entonces no necesitamos voltear el bit pero si C[i] == 0, entonces necesitamos voltear el bit en A[i] o B[i] para que 0^0==0 o 1^1==0
C++
// C++ code to count the Minimum bits in A and B
#include<bits/stdc++.h>
using namespace std;
int totalFlips(char *A, char *B, char *C, int N)
{
int count = 0;
for (int i=0; i < N; ++i)
{
// If both A[i] and B[i] are equal
if (A[i] == B[i] && C[i] == '1')
++count;
// If Both A and B are unequal
else if (A[i] != B[i] && C[i] == '0')
++count;
}
return count;
}
//Driver Code
int main()
{
//N represent total count of Bits
int N = 5;
char a[] = "10100";
char b[] = "00010";
char c[] = "10011";
cout << totalFlips(a, b, c, N);
return 0;
}
Java
// Java code to count the Minimum bits in A and B
class GFG {
static int totalFlips(String A, String B,
String C, int N)
{
int count = 0;
for (int i = 0; i < N; ++i)
{
// If both A[i] and B[i] are equal
if (A.charAt(i) == B.charAt(i) &&
C.charAt(i) == '1')
++count;
// If Both A and B are unequal
else if (A.charAt(i) != B.charAt(i)
&& C.charAt(i) == '0')
++count;
}
return count;
}
//driver code
public static void main (String[] args)
{
//N represent total count of Bits
int N = 5;
String a = "10100";
String b = "00010";
String c = "10011";
System.out.print(totalFlips(a, b, c, N));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python code to find minimum bits to be flip def totalFlips(A, B, C, N): count = 0 for i in range(N): # If both A[i] and B[i] are equal if A[i] == B[i] and C[i] == '1': count=count+1 # if A[i] and B[i] are unequal else if A[i] != B[i] and C[i] == '0': count=count+1 return count # Driver Code # N represent total count of Bits N = 5 a = "10100" b = "00010" c = "10011" print(totalFlips(a, b, c, N))
C#
// C# code to count the Minimum
// bits flip in A and B
using System;
class GFG {
static int totalFlips(string A, string B,
string C, int N)
{
int count = 0;
for (int i = 0; i < N; ++i) {
// If both A[i] and B[i] are equal
if (A[i] == B[i] && C[i] == '1')
++count;
// If Both A and B are unequal
else if (A[i] != B[i] && C[i] == '0')
++count;
}
return count;
}
// Driver code
public static void Main()
{
// N represent total count of Bits
int N = 5;
string a = "10100";
string b = "00010";
string c = "10011";
Console.Write(totalFlips(a, b, c, N));
}
}
// This code is contributed by Anant Agarwal.
PHP
<?php
// PHP code to count the
// Minimum bits in A and B
function totalFlips($A, $B, $C, $N)
{
$count = 0;
for ($i = 0; $i < $N; ++$i)
{
// If both A[i] and
// B[i] are equal
if ($A[$i] == $B[$i] &&
$C[$i] == '1')
++$count;
// If Both A and
// B are unequal
else if ($A[$i] != $B[$i] &&
$C[$i] == '0')
++$count;
}
return $count;
}
// Driver Code
// N represent total count of Bits
$N = 5;
$a = "10100";
$b = "00010";
$c = "10011";
echo totalFlips($a, $b, $c, $N);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// Javascript code to count the Minimum bits in A and B
function totalFlips(A, B, C, N)
{
let count = 0;
for (let i = 0; i < N; ++i) {
// If both A[i] and B[i] are equal
if (A[i] == B[i] && C[i] == '1')
++count;
// If Both A and B are unequal
else if (A[i] != B[i] && C[i] == '0')
++count;
}
return count;
}
// Driver Code
// N represent total count of Bits
let N = 5;
let a = "10100";
let b = "00010";
let c = "10011";
document.write(totalFlips(a, b, c, N));
</script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente:
Este enfoque sigue la complejidad de tiempo O (log N).
C++
// C++ code to count the Minimum bits in A and B
#include <bits/stdc++.h>
using namespace std;
int totalFlips(string A, string B, string C, int N)
{
int INTSIZE = 31;
int ans = 0;
int i = 0;
while (N > 0) {
// Considering only 31 bits
int a = stoi(A.substr(i * INTSIZE, min(INTSIZE, N)),
0, 2);
int b = stoi(B.substr(i * INTSIZE, min(INTSIZE, N)),
0, 2);
int c = stoi(C.substr(i * INTSIZE, min(INTSIZE, N)),
0, 2);
int Z = a ^ b ^ c;
// builtin function for
// counting the number of set bits.
ans += __builtin_popcount(Z);
i++;
N -= 32;
}
return ans;
}
// Driver Code
int main()
{
// N represent total count of Bits
int N = 5;
char a[] = "10100";
char b[] = "00010";
char c[] = "10011";
cout << totalFlips(a, b, c, N);
return 0;
}
// This code is contributed by Kasina Dheeraj.
Java
// Java code to count the Minimum bits in A and B
class GFG {
static int totalFlips(String A, String B, String C,
int N)
{
int INTSIZE = 31;
int ans = 0;
int i = 0;
while (N > 0) {
// Considering only 31 bits
int a = Integer.parseInt(
A.substring(i * INTSIZE,
i * INTSIZE
+ Math.min(INTSIZE, N)),
2);
int b = Integer.parseInt(
B.substring(i * INTSIZE,
i * INTSIZE
+ Math.min(INTSIZE, N)),
2);
int c = Integer.parseInt(
C.substring(i * INTSIZE,
i * INTSIZE
+ Math.min(INTSIZE, N)),
2);
int Z = a ^ b ^ c;
// builtin function for
// counting the number of set bits.
ans += Integer.bitCount(Z);
i++;
N -= 32;
}
return ans;
}
// driver code
public static void main(String[] args)
{
// N represent total count of Bits
int N = 5;
String a = "10100";
String b = "00010";
String c = "10011";
System.out.print(totalFlips(a, b, c, N));
}
}
// This code is contributed by Kasina Dheeraj.
2
¿Por qué funciona este código?
Observamos que el bit debe invertirse si A[i]^B[i] !=C[i]. Entonces, podemos obtener el número de vueltas calculando el número de bits establecidos en a^b^c donde a,b,c son representaciones enteras de strings binarias. Pero la longitud de la string puede ser superior a 32, el tamaño de un tipo int típico. Entonces, el plan es dividir la string en substrings de longitud 31, realizar operaciones y contar los bits establecidos como se menciona para cada substring.
Complejidad de tiempo: O(log N) a medida que el ciclo while se ejecuta para log 31 N veces y el conteo de bits establecidos cuenta como máximo O(32) para 32 bits y O(64) para 64 bits y para cada operación de substring O( 31).
Complejidad espacial: O(1), para tener en cuenta que la operación de substring necesita espacio O(32).
Este artículo es una contribución de Shubham Bansal y Kasina Dheeraj . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente”.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA