Given two positive integers A and B, the task is to calculate the minimum number of operations required such that Bitwise OR of A and B equals Bitwise AND of A and B are equal i.e (A&B)=(A|B), where, in each operation two indices i and j are chosen and the ith bit of A is swapped with the jth bit of B. If it is not possible to make (A&B)=(A|B), print -1.
Examples:
Input: A = 1, B = 2
Output: 2
Explanation:
A10 ≡ 012, B10 ≡ 102
The following sequence of moves can be performed:
- i = 1, j = 1⇒ A = 11, B = 00 (A|B = 3, A&B = 0).
- i = 1, j = 0⇒ A = 01, B = 01 (A|B = 1, A&B = 1).
Thus, 2 moves are required.
Input: A = 27, B = 5
Output: 3
Explanation:
A10 ≡ 110112, B10 ≡ 001012
The following sequence of moves can be performed:
- i = 4, j = 3⇒ A = 01011, B = 01101 (A|B = 15, A&B = 9).
- i = 2, j = 2⇒ A = 01111, B = 01001 (A|B = 15, A&B = 9).
- i = 2, j = 1⇒ A = 01011, B = 01011 (A|B = 11, A&B = 11).
Thus, 3 moves are required.
Approach:
Observation: The main observation to solve this problem is that for (A&B)=(A|B) is that A must be equal to B because if only two bits are set, then only their Bitwise AND and Bitwise OR are equal.
Follow the below steps to solve the problem:
- Count the number of total set bits in A and B.
- If the count is odd, the two numbers cannot be made equal, so print -1.
- Initialize two counters oneZero=0 and zeroOne=0
- Traverse through the bits of A and B, and do the following:
- If current bit of A is set and current bit of B is unset i.e (1, 0), increment oneZero.
- If current bit of A is unset and current bit of B is set i.e (0, 1), increment zeroOne.
- To minimize the number of operations required, it is optimal to choose two (1, 0) or two (0, 1) indices and swap either one of them, i.e only half of oneZero and zeroOne operations are required.
- If oneZero is odd(which means zeroOne is also odd), two more operations would be required to turn (0, 1) and a (1, 0) to (1, 1) and (0, 0)
- So, the final answer is (oneZero/2)+(zeroOne/2)+(oneZero%2?2:0).
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function for counting number of set bitint countSetBits(int n){ int count = 0; while (n) { n = n & (n - 1); count++; } return count;}// Function to return the count of// minimum operations requiredint minOperations(int A, int B){ // cnt to count the number of bits // set in A and in B int cnt1 = 0, cnt2 = 0; cnt1 += countSetBits(A); cnt2 += countSetBits(B); // if odd numbers of total set bits if ((cnt1 + cnt2) % 2 != 0) return -1; // one_zero = 1 in A and 0 in B at ith bit // similarly for zero_one int oneZero = 0, zeroOne = 0; int ans = 0; for (int i = 0; i < max(cnt1, cnt2); i++) { int bitpos = 1 << i; // When bitpos is set in B, unset in B if ((!(bitpos & A)) && (bitpos & B)) zeroOne++; // When bitpos is set in A, unset in B if ((bitpos & A) && (!(bitpos & B))) oneZero++; } // number of moves is half of // number pairs of each group ans = (zeroOne / 2) + (oneZero / 2); // odd number pairs if (zeroOne % 2 != 0) ans += 2; return ans;}// Driver codeint main(){ // Input int A = 27, B = 5; // Function call to compute the result cout << minOperations(A, B); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function for counting number of set bitstatic int countSetBits(int n){ int count = 0; while (n != 0) { n = n & (n - 1); count++; } return count;}// Function to return the count of// minimum operations requiredstatic int minOperations(int A, int B){ // cnt to count the number of bits // set in A and in B int cnt1 = 0, cnt2 = 0; cnt1 += countSetBits(A); cnt2 += countSetBits(B); // if odd numbers of total set bits if ((cnt1 + cnt2) % 2 != 0) return -1; // one_zero = 1 in A and 0 in B at ith bit // similarly for zero_one int oneZero = 0, zeroOne = 0; int ans = 0; for (int i = 0; i < Math.max(cnt1, cnt2); i++) { int bitpos = 1 << i; // When bitpos is set in B, unset in B if (((bitpos & A) == 0) && ((bitpos & B) != 0)) zeroOne++; // When bitpos is set in A, unset in B if (((bitpos & A) != 0) && ((bitpos & B) == 0)) oneZero++; } // number of moves is half of // number pairs of each group ans = (zeroOne / 2) + (oneZero / 2); // odd number pairs if (zeroOne % 2 != 0) ans += 2; return ans;}// Driver Codepublic static void main(String args[]){ // Input int A = 27, B = 5; // Function call to compute the result System.out.println( minOperations(A, B));}}// This code is contributed by splevel62. |
Python3
# Python3 implementation of the above approach# Function for counting number of set bitdef countSetBits(n): count = 0 while (n): n = n & (n - 1) count += 1 return count # Function to return the count of# minimum operations requireddef minOperations(A, B): # cnt to count the number of bits # set in A and in B cnt1 = 0 cnt2 = 0 cnt1 += countSetBits(A) cnt2 += countSetBits(B) # If odd numbers of total set bits if ((cnt1 + cnt2) % 2 != 0): return -1 # one_zero = 1 in A and 0 in B at ith bit # similarly for zero_one oneZero = 0 zeroOne = 0 ans = 0 for i in range(max(cnt1, cnt2)): bitpos = 1 << i # When bitpos is set in B, unset in B if ((not(bitpos & A)) and (bitpos & B)): zeroOne += 1 # When bitpos is set in A, unset in B if ((bitpos & A) and (not(bitpos & B))): oneZero += 1 # Number of moves is half of # number pairs of each group ans = (zeroOne // 2) + (oneZero // 2) # Odd number pairs if (zeroOne % 2 != 0): ans += 2 return ans# Driver codeif __name__ == '__main__': # Input A = 27 B = 5 # Function call to compute the result print(minOperations(A, B)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;class GFG{// Function for counting number of set bitstatic int countSetBits(int n){ int count = 0; while (n > 0) { n = n & (n - 1); count++; } return count;}// Function to return the count of// minimum operations requiredstatic int minOperations(int A, int B){ // cnt to count the number of bits // set in A and in B int cnt1 = 0, cnt2 = 0; cnt1 += countSetBits(A); cnt2 += countSetBits(B); // If odd numbers of total set bits if ((cnt1 + cnt2) % 2 != 0) return -1; // one_zero = 1 in A and 0 in B at ith bit // similarly for zero_one int oneZero = 0, zeroOne = 0; int ans = 0; for(int i = 0; i < Math.Max(cnt1, cnt2); i++) { int bitpos = 1 << i; // When bitpos is set in B, unset in B if (((bitpos & A) == 0) && (bitpos & B) != 0) zeroOne++; // When bitpos is set in A, unset in B if ((bitpos & A) != 0 && ((bitpos & B) == 0)) oneZero++; } // Number of moves is half of // number pairs of each group ans = (zeroOne / 2) + (oneZero / 2); // Odd number pairs if (zeroOne % 2 != 0) ans += 2; return ans;}// Driver codepublic static void Main(){ // Input int A = 27, B = 5; // Function call to compute the result Console.Write(minOperations(A, B));}}// This code is contributed by bgangwar59 |
Javascript
<script>// JavaScript implementation of the above approach// Function for counting number of set bitfunction countSetBits(n){ let count = 0; while (n) { n = n & (n - 1); count++; } return count;}// Function to return the count of// minimum operations requiredfunction minOperations(A, B){ // cnt to count the number of bits // set in A and in B let cnt1 = 0, cnt2 = 0; cnt1 += countSetBits(A); cnt2 += countSetBits(B); // if odd numbers of total set bits if ((cnt1 + cnt2) % 2 != 0) return -1; // one_zero = 1 in A and 0 in B at ith bit // similarly for zero_one let oneZero = 0, zeroOne = 0; let ans = 0; for (let i = 0; i < Math.max(cnt1, cnt2); i++) { let bitpos = 1 << i; // When bitpos is set in B, unset in B if ((!(bitpos & A)) && (bitpos & B)) zeroOne++; // When bitpos is set in A, unset in B if ((bitpos & A) && (!(bitpos & B))) oneZero++; } // number of moves is half of // number pairs of each group ans = parseInt(zeroOne / 2) + parseInt(oneZero / 2); // odd number pairs if (zeroOne % 2 != 0) ans += 2; return ans;}// Driver code // Input let A = 27, B = 5; // Function call to compute the result document.write(minOperations(A, B)); </script> |
Output
3
Time Complexity: O(Log2N)
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!
