Dados tres números enteros positivos X , Y y Z , la tarea es contar el número mínimo de bits necesarios para invertir en X e Y de modo que X OR Y (X | Y) sea igual a Z .
Ejemplos:
Input : X = 5 Y = 8 Z = 6
Output : 3
Explanation :
Before After
Flipping Flipping
X :: 0101 0100
Y :: 1000 0010
------ -----
Z :: 0110 0110
So we need to flip 3 bits in order
to make (X | Y) = Z .
Input : X = 1 Y = 2 Z = 3
Output : 0
Enfoque:
para resolver este problema, debemos observar que la necesidad de cambiar un bit X o Y surge solo para las siguientes condiciones:
- Si el bit actual en Z está configurado y el bit correspondiente en X e Y no está configurado, debemos configurar un bit en X o en Y.
- Si el bit actual en Z no está configurado, debemos desactivar el bit correspondiente en A y B, cualquiera que esté configurado. Desarmar ambos si ambos están armados.
Por lo tanto, debemos atravesar los bits de X, Y y Z y seguir los dos pasos anteriores para obtener el resultado deseado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to minimize
// number of bits to be flipped
// in X or Y such that their
// bitwise or is equal to minimize
#include <bits/stdc++.h>
using namespace std;
// This function returns minimum
// number of bits to be flipped in
// X and Y to make X | Y = Z
int minimumFlips(int X, int Y, int Z)
{
int res = 0;
while (X > 0 || Y > 0 || Z > 0) {
// If current bit in Z is set and is
// also set in either of X or Y or both
if (((X & 1) || (Y & 1)) && (Z & 1)) {
X = X >> 1;
Y = Y >> 1;
Z = Z >> 1;
continue;
}
// If current bit in Z is set
// and is unset in both X and Y
else if (!(X & 1) && !(Y & 1) && (Z & 1)) {
// Set that bit in either X or Y
res++;
}
else if ((X & 1) || (Y & 1) == 1)
{
// If current bit in Z is unset
// and is set in both X and Y
if ((X & 1) && (Y & 1) && !(Z & 1)) {
// Unset the bit in both X and Y
res += 2;
}
// If current bit in Z is unset and
// is set in either X or Y
else if (((X & 1) || (Y & 1)) && !(Z & 1))
{
// Unset that set bit
res++;
}
}
X = X >> 1;
Y = Y >> 1;
Z = Z >> 1;
}
return res;
}
// Driver Code
int main()
{
int X = 5, Y = 8, Z = 6;
cout << minimumFlips(X, Y, Z);
return 0;
}
Java
// Java program to minimize
// number of bits to be flipped
// in X or Y such that their
// bitwise or is equal to minimize
import java.util.*;
class GFG{
// This function returns minimum
// number of bits to be flipped in
// X and Y to make X | Y = Z
static int minimumFlips(int X, int Y, int Z)
{
int res = 0;
while (X > 0 || Y > 0 || Z > 0)
{
// If current bit in Z is set and is
// also set in either of X or Y or both
if (((X % 2 == 1) ||
(Y % 2 == 1)) &&
(Z % 2 == 1))
{
X = X >> 1;
Y = Y >> 1;
Z = Z >> 1;
continue;
}
// If current bit in Z is set
// and is unset in both X and Y
else if (!(X % 2 == 1) &&
!(Y % 2 == 1) &&
(Z % 2 == 1))
{
// Set that bit in either X or Y
res++;
}
else if ((X % 2 == 1) || (Y % 2 == 1))
{
// If current bit in Z is unset
// and is set in both X and Y
if ((X % 2 == 1) &&
(Y % 2 == 1) &&
!(Z % 2 == 1))
{
// Unset the bit in both X and Y
res += 2;
}
// If current bit in Z is unset and
// is set in either X or Y
else if (((X % 2 == 1) ||
(Y % 2 == 1)) &&
!(Z % 2 == 1))
{
// Unset that set bit
res++;
}
}
X = X >> 1;
Y = Y >> 1;
Z = Z >> 1;
}
return res;
}
// Driver Code
public static void main(String[] args)
{
int X = 5, Y = 8, Z = 6;
System.out.print(minimumFlips(X, Y, Z));
}
}
// This code is contributed by amal kumar choubey
Python3
# Python 3 Program to minimize # number of bits to be flipped # in X or Y such that their # bitwise or is equal to minimize # This function returns minimum # number of bits to be flipped in # X and Y to make X | Y = Z def minimumFlips(X, Y, Z): res = 0 while (X > 0 or Y > 0 or Z > 0): # If current bit in Z is # set and is also set in # either of X or Y or both if (((X & 1) or (Y & 1)) and (Z & 1)): X = X >> 1 Y = Y >> 1 Z = Z >> 1 continue # If current bit in Z is set # and is unset in both X and Y elif (not (X & 1) and not(Y & 1) and (Z & 1)): # Set that bit in either # X or Y res += 1 elif ((X & 1) or (Y & 1) == 1): # If current bit in Z is unset # and is set in both X and Y if ((X & 1) and (Y & 1) and not(Z & 1)): # Unset the bit in both # X and Y res += 2 # If current bit in Z is # unset and is set in # either X or Y elif (((X & 1) or (Y & 1)) and not(Z & 1)): # Unset that set bit res += 1 X = X >> 1 Y = Y >> 1 Z = Z >> 1 return res # Driver Code if __name__ == "__main__": X = 5 Y = 8 Z = 6 print(minimumFlips(X, Y, Z)) # This code is contributed by Chitranayal
C#
// C# program to minimize
// number of bits to be flipped
// in X or Y such that their
// bitwise or is equal to minimize
using System;
class GFG{
// This function returns minimum
// number of bits to be flipped in
// X and Y to make X | Y = Z
static int minimumFlips(int X, int Y, int Z)
{
int res = 0;
while (X > 0 || Y > 0 || Z > 0)
{
// If current bit in Z is set and is
// also set in either of X or Y or both
if (((X % 2 == 1) ||
(Y % 2 == 1)) &&
(Z % 2 == 1))
{
X = X >> 1;
Y = Y >> 1;
Z = Z >> 1;
continue;
}
// If current bit in Z is set
// and is unset in both X and Y
else if (!(X % 2 == 1) &&
!(Y % 2 == 1) &&
(Z % 2 == 1))
{
// Set that bit in either X or Y
res++;
}
else if ((X % 2 == 1) || (Y % 2 == 1))
{
// If current bit in Z is unset
// and is set in both X and Y
if ((X % 2 == 1) &&
(Y % 2 == 1) &&
!(Z % 2 == 1))
{
// Unset the bit in both X and Y
res += 2;
}
// If current bit in Z is unset and
// is set in either X or Y
else if (((X % 2 == 1) ||
(Y % 2 == 1)) &&
!(Z % 2 == 1))
{
// Unset that set bit
res++;
}
}
X = X >> 1;
Y = Y >> 1;
Z = Z >> 1;
}
return res;
}
// Driver Code
public static void Main()
{
int X = 5, Y = 8, Z = 6;
Console.Write(minimumFlips(X, Y, Z));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript Program to minimize
// number of bits to be flipped
// in X or Y such that their
// bitwise or is equal to minimize
// This function returns minimum
// number of bits to be flipped in
// X and Y to make X | Y = Z
function minimumFlips(X, Y, Z)
{
var res = 0;
while (X > 0 || Y > 0 || Z > 0) {
// If current bit in Z is set and is
// also set in either of X or Y or both
if (((X & 1) || (Y & 1)) && (Z & 1))
{
X = X >> 1;
Y = Y >> 1;
Z = Z >> 1;
continue;
}
// If current bit in Z is set
// and is unset in both X and Y
else if ((X & 1)==0 && (Y & 1)==0 &&
(Z & 1))
{
// Set that bit in either X or Y
res++;
}
else if ((X & 1) || (Y & 1) == 1)
{
// If current bit in Z is unset
// and is set in both X and Y
if ((X & 1) && (Y & 1) && (Z & 1)==0)
{
// Unset the bit in both X and Y
res += 2;
}
// If current bit in Z is unset and
// is set in either X or Y
else if (((X & 1) || (Y & 1)) &&
(Z & 1)==0)
{
// Unset that set bit
res++;
}
}
X = X >> 1;
Y = Y >> 1;
Z = Z >> 1;
}
return res;
}
// Driver Code
var X = 5, Y = 8, Z = 6;
document.write(minimumFlips(X, Y, Z));
</script>
Producción:
3
Publicación traducida automáticamente
Artículo escrito por ankitkumar83346 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA