Given three positive integers X, Y and Z, the task is to count the minimum numbers of bits required to be flipped in X and Y such that X OR Y (X | Y) is equal to Z.
Examples:
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
Approach :
In order to solve this problem, we need to observe that the need to flip a bit X or Y arises only for the following conditions:
- If the current bit in Z is set and the corresponding bit in both X and Y is not set, we need to set a bit in either X or in Y.
- If the current bit in Z is unset, we need to unset the corresponding bit in A and B, whichever is set. Unset both if both are set.
Thus, we need to traverse through the bits of X, Y, and Z and follow the above two steps to get the desired result.
Below is the implementation of the above approach:
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 = Zint 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 Codeint 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 minimizeimport java.util.*;class GFG{// This function returns minimum // number of bits to be flipped in// X and Y to make X | Y = Zstatic 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 Codepublic 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 = Zdef 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 Codeif __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 minimizeusing System;class GFG{// This function returns minimum // number of bits to be flipped in// X and Y to make X | Y = Zstatic 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 Codepublic 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 = Zfunction 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> |
Output:
3
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
