Dados tres enteros positivos A , B y C , la tarea es contar el número mínimo de cambios de bits requeridos en A y B , de modo que el OR de A y B sea igual a C o no.
Ejemplos:
Entrada: A = 2, B = 2, C = 3
Salida: 1
Explicación:
La representación binaria de A es 010, B es 010 y C es 011.
Voltee el tercer bit de A o B, de modo que A | B = C, es decir, 011 | 010 = 011.
Por lo tanto, el número total de lanzamientos necesarios es 1.Entrada: A = 2, B = 6, C = 5
Salida: 3
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos res , que almacene el número mínimo de bits volteados requeridos.
- Iterar sobre cada bit de A , B y C y realizar los siguientes pasos:
- Si el i -ésimo bit de C no está configurado, verifique lo siguiente:
- Si se establece el i -ésimo bit de A , incremente res con 1 , el i -ésimo bit de A debe invertirse.
- Si se establece el i -ésimo bit de B , incremente res con 1 , es necesario invertir el i -ésimo bit de B.
- Si el i -ésimo bit de C está configurado, verifique lo siguiente:
- Si el i -ésimo bit de A y B no está configurado, incremente res con 1 , cualquiera de los bits debe invertirse.
- Si se establece el i -ésimo bit de A y B , no tenemos que cambiar ninguno de los bits.
- Si el i -ésimo bit de C no está configurado, verifique lo siguiente:
- Después de completar los pasos anteriores, imprima el valor de res como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the number of // bit flips required on A and B // such that Bitwise OR of A and B is C int minimumFlips(int A, int B, int C) { // Stores the count of flipped bit int res = 0; // Iterate over the range [0, 32] for (int i = 0; i < 32; i++) { int x = 0, y = 0, z = 0; // Check if i-th bit of A is set if (A & (1 << i)) { x = 1; } // Check if i-th bit of B is // set or not if (B & (1 << i)) { y = 1; } // Check if i-th bit of C is // set or not if (C & (1 << i)) { z = 1; } // If i-th bit of C is unset if (z == 0) { // Check if i-th bit of // A is set or not if (x) { res++; } // Check if i-th bit of // B is set or not if (y) { res++; } } // Check if i-th bit of C // is set or not if (z == 1) { // Check if i-th bit of // both A and B is set if (x == 0 && y == 0) { res++; } } } // Return the count // of bits flipped return res; } // Driver Code int main() { int A = 2, B = 6, C = 5; cout << minimumFlips(A, B, C); return 0; }
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ // Function to count the number of // bit flips required on A and B // such that Bitwise OR of A and B is C static int minimumFlips(int A, int B, int C) { // Stores the count of flipped bit int res = 0; // Iterate over the range [0, 32] for(int i = 0; i < 32; i++) { int x = 0, y = 0, z = 0; // Check if i-th bit of A is set if ((A & (1 << i)) != 0) { x = 1; } // Check if i-th bit of B is // set or not if ((B & (1 << i)) != 0) { y = 1; } // Check if i-th bit of C is // set or not if ((C & (1 << i)) != 0) { z = 1; } // If i-th bit of C is unset if (z == 0) { // Check if i-th bit of // A is set or not if (x == 1) { res++; } // Check if i-th bit of // B is set or not if (y == 1) { res++; } } // Check if i-th bit of C // is set or not if (z == 1) { // Check if i-th bit of // both A and B is set if (x == 0 && y == 0) { res++; } } } // Return the count // of bits flipped return res; } // Driver Code public static void main(String[] args) { int A = 2, B = 6, C = 5; System.out.println(minimumFlips(A, B, C)); } } // This code is contributed by Kingash
Python3
# Python3 program for the above approach # Function to count the number of # bit flips required on A and B # such that Bitwise OR of A and B is C def minimumFlips(A, B, C): # Stores the count of flipped bit res = 0 # Iterate over the range [0, 32] for i in range(32): x, y, z = 0, 0, 0 # Check if i-th bit of A is set if (A & (1 << i)): x = 1 # Check if i-th bit of B is # set or not if (B & (1 << i)): y = 1 # Check if i-th bit of C is # set or not if (C & (1 << i)): z = 1 # If i-th bit of C is unset if (z == 0): # Check if i-th bit of # A is set or not if (x): res += 1 # Check if i-th bit of # B is set or not if (y): res += 1 # Check if i-th bit of C # is set or not if (z == 1): # Check if i-th bit of # both A and B is set if (x == 0 and y == 0): res += 1 # Return the count # of bits flipped return res # Driver Code if __name__ == '__main__': A, B, C = 2, 6, 5 print(minimumFlips(A, B, C)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach using System; class GFG { // Function to count the number of // bit flips required on A and B // such that Bitwise OR of A and B is C static int minimumFlips(int A, int B, int C) { // Stores the count of flipped bit int res = 0; // Iterate over the range [0, 32] for (int i = 0; i < 32; i++) { int x = 0, y = 0, z = 0; // Check if i-th bit of A is set if ((A & (1 << i)) != 0) { x = 1; } // Check if i-th bit of B is // set or not if ((B & (1 << i)) != 0) { y = 1; } // Check if i-th bit of C is // set or not if ((C & (1 << i)) != 0) { z = 1; } // If i-th bit of C is unset if (z == 0) { // Check if i-th bit of // A is set or not if (x == 1) { res++; } // Check if i-th bit of // B is set or not if (y == 1) { res++; } } // Check if i-th bit of C // is set or not if (z == 1) { // Check if i-th bit of // both A and B is set if (x == 0 && y == 0) { res++; } } } // Return the count // of bits flipped return res; } // Driver Code public static void Main(string[] args) { int A = 2, B = 6, C = 5; Console.WriteLine(minimumFlips(A, B, C)); } } // This code is contributed by ukasp.
Javascript
<script> // javascript program for the above approach // Function to count the number of // bit flips required on A and B // such that Bitwise OR of A and B is C function minimumFlips(A , B , C) { // Stores the count of flipped bit var res = 0; // Iterate over the range [0, 32] for (i = 0; i < 32; i++) { var x = 0, y = 0, z = 0; // Check if i-th bit of A is set if ((A & (1 << i)) != 0) { x = 1; } // Check if i-th bit of B is // set or not if ((B & (1 << i)) != 0) { y = 1; } // Check if i-th bit of C is // set or not if ((C & (1 << i)) != 0) { z = 1; } // If i-th bit of C is unset if (z == 0) { // Check if i-th bit of // A is set or not if (x == 1) { res++; } // Check if i-th bit of // B is set or not if (y == 1) { res++; } } // Check if i-th bit of C // is set or not if (z == 1) { // Check if i-th bit of // both A and B is set if (x == 0 && y == 0) { res++; } } } // Return the count // of bits flipped return res; } // Driver Code var A = 2, B = 6, C = 5; document.write(minimumFlips(A, B, C)); // This code is contributed by aashish1995 </script>
3
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por nirajgusain5 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA