Given three positives integers A, B, and C, the task is to count the minimum number of flipping of bits required in A and B, such that the Bitwise OR of A and B is equal to C or not.
Examples:
Input: A = 2, B = 2, C = 3
Output: 1
Explanation:
The binary representation of A is 010, B is 010 and C is 011.
Flip the 3rd bit of either A or B, such that A | B = C, i.e. 011 | 010 = 011.
Therefore, the total number of flips required is 1.Input: A = 2, B = 6, C = 5
Output: 3
Approach: Follow the steps below to solve the problem:
- Initialize a variable, say res, that stores the minimum number of the flipped bits required.
- Iterate over each bit of A, B, and C and perform the following steps:
- If the ith bit of C is not set, then check for the following:
- If the ith bit of A is set, increment res with 1, ith bit of A needs to be flipped.
- If the ith bit of B is set, increment res with 1, ith bit of B needs to be flipped.
- If the ith bit of C is set, then check for the following:
- If the ith bit of both A and B are not set, increment res with 1, either of the bit needs to be flipped.
- If the ith bit of both A and B are set, we do not have to flip any of the bits.
- If the ith bit of C is not set, then check for the following:
- After completing the above steps, print the value of res as the result.
Below is the implementation of the above approach:
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 Cint 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 Codeint main(){ int A = 2, B = 6, C = 5; cout << minimumFlips(A, B, C); return 0;} |
Java
// Java program for the above approachimport 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 Cstatic 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 Codepublic 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 Cdef 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 Codeif __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 approachusing 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> |
Output:
3
Time Complexity: O(1)
Auxiliary Space: O(1)
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!
