Given two n-bit integers a and b, find the maximum possible value of (a’ xor b’) where a’ is a shuffle-a, b’ is a shuffle-b and xor is the bitwise xor operator.
Note: Consider a n-bit integer a. We call an integer a’ as shuffle-a if a’ can be obtained by shuffling the bits of a in its binary representation. For eg. if n = 5 and a = 6 = (00110)2, a’ can be any 5-bit integer having exactly two 1s in it i.e., any of (00011)2, (00101)2, (00110)2, (01010)2, …., (11000)2.
Examples:
Input: n = 3, a = 5, b = 4
Output: 7
Explanation: a = (101)2, b = (100)2, a’ = (110)2 , b’ = (001)2 and a’ xor b’ = (111)2Input: n = 5, a = 0, b = 1
Output: 16
Explanation: a = (00000)2 , b = (00001)2 a’ = (00000)2 , b = (10000)2 and a’ xor b’ = (10000)2
Approach: To solve the problem follow the below steps:
- Count the number of set bits in both a and b.
- Then, compute minimum (set bit count in a, zeroes in b) and minimum (set bit count in b, zeroes in a).
- The summation(sum) of these two values gives the total number of set bits possible in a’ xor b’.
The above formula works for every possible a and b because:
- We want to maximize our answer, hence we find out the maximum number of 1’s it can contain. In XOR operations, if a particular bit position has a 1 in one number and a 0 in the other number, the result will have a 1 in that position (1^0=1 and 0^1=1). So, we find the maximum number of 1-0 and 0-1 pairs. The function min(1’s in a , 0’s in b) gives the maximum 1-0 pairs possible and the function min(0’s in a , 1’s in b) gives the maximum 0-1 pairs possible. Their sum will give the maximum number of 1’s possible in our answer.
- Example: n = 4, a = 10, b = 13 a’ = 1010, b’ = 1101
- Minimum(set bit count in a, zeroes in b) = 1, Minimum(set bit count in b, zeroes in a) = 2
- Total set bits in a’ xor b'(sum) -> 1 + 2 = 3
- One of the possible a’ and b’ combinations is a’=1001, b’= 0111 a’ xor b’ = 1110 = 14, which is the maximum possible value.
- It is clear that 3 is the total number of bits to maximize xor.
- Inside the for loop, it computes the maximum possible value of a’ xor b’ by placing all the set bits(= to sum) in the beginning followed by zeroes
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int MaximumXor(int a, int b, int n){ int count1 = 0, count2 = 0; // Count the number of set bits in a while (a) { if (a & 1) count1++; a = a >> 1; } // Count the number of set bits in b while (b) { if (b & 1) count2++; b = b >> 1; } // Minimum of set bit count in a // and zeroes in b int m1 = min(count1, n - count2); // Minimum of set bit count in b and // zeroes in a int m2 = min(n - count1, count2); // The total number of set bits in // a' xor b' int sum = (m1 + m2); double XOR = 0; // Compute the maximum possible // value of a' xor b' for (int i = 1; i <= sum; i++) { XOR = XOR + pow(2, n - 1); n--; } return (int)XOR;}// Drivers codeint main(){ int n, a, b; n = 3, a = 5, b = 4; // Functional call cout << MaximumXor(a, b, n) << "\n"; return 0;} |
Java
import java.util.*;public class Main { public static void main(String[] args) { int n, a, b; n = 3; a = 5; b = 4; // Functional call System.out.println(MaximumXor(a, b, n)); } public static int MaximumXor(int a, int b, int n) { int count1 = 0, count2 = 0; // Count the number of set bits in a while (a != 0) { if ((a & 1) == 1) count1++; a = a >> 1; } // Count the number of set bits in b while (b != 0) { if ((b & 1) == 1) count2++; b = b >> 1; } // Minimum of set bit count in a // and zeroes in b int m1 = Math.min(count1, n - count2); // Minimum of set bit count in b and // zeroes in a int m2 = Math.min(n - count1, count2); // The total number of set bits in // a' xor b' int sum = (m1 + m2); double XOR = 0; // Compute the maximum possible // value of a' xor b' for (int i = 1; i <= sum; i++) { XOR = XOR + Math.pow(2, n - 1); n--; } return (int) XOR; }} |
Python3
def MaximumXor(a, b, n): count1 = 0 count2 = 0 # Count the number of set bits in a while a: if a & 1: count1 += 1 a = a >> 1 # Count the number of set bits in b while b: if b & 1: count2 += 1 b = b >> 1 # Minimum of set bit count in a # and zeroes in b m1 = min(count1, n - count2) # Minimum of set bit count in b and # zeroes in a m2 = min(n - count1, count2) # The total number of set bits in # a' xor b' sum = m1 + m2 XOR = 0 # Compute the maximum possible # value of a' xor b' for i in range(1, sum + 1): XOR = XOR + pow(2, n - 1) n -= 1 return int(XOR)# Drivers coden = 3a = 5b = 4# Functional callprint(MaximumXor(a, b, n))# This code is contributed by Sakshi |
C#
using System;namespace GFG{ class Geek { static int MaximumXor(int a, int b, int n) { int count1 = 0, count2 = 0; // Count the number of // set bits in a while (a > 0) { if ((a & 1) == 1) count1++; a >>= 1; } // Count the number of // set bits in b while (b > 0) { if ((b & 1) == 1) count2++; b >>= 1; } // Minimum of set bit count in a // and zeroes in b int m1 = Math.Min(count1, n - count2); // Minimum of set bit count in b and // zeroes in a int m2 = Math.Min(n - count1, count2); int sum = (m1 + m2); double XOR = 0; // Compute the maximum possible // value of a' xor b' for (int i = 1; i <= sum; i++) { XOR += Math.Pow(2, n - 1); n--; } return (int)XOR; } static void Main(string[] args) { int n = 3, a = 5, b = 4; // Functional call Console.WriteLine(MaximumXor(a, b, n)); } }} |
Javascript
// Javascript code for the above approachfunction MaximumXor(a, b, n) { let count1 = 0, count2 = 0; // Count the number of set bits in a while (a !== 0) { if ((a & 1) === 1) count1++; a = a >> 1; } // Count the number of set bits in b while (b !== 0) { if ((b & 1) === 1) count2++; b = b >> 1; } // Minimum of set bit count in a // and zeroes in b let m1 = Math.min(count1, n - count2); // Minimum of set bit count in b and // zeroes in a let m2 = Math.min(n - count1, count2); // The total number of set bits in // a' xor b' let sum = (m1 + m2); let XOR = 0; // Compute the maximum possible // value of a' xor b' for (let i = 1; i <= sum; i++) { XOR = XOR + Math.pow(2, n - 1); n--; } return XOR;}// Drivers codelet n, a, b;n = 3;a = 5;b = 4;// Functional callconsole.log(MaximumXor(a, b, n));// This code is contributed by ragul21 |
Output
7
Time complexity: O(n), where n is the length of the binary number
Auxiliary Space: O(1) as constant space is used.
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!
Share your thoughts in the comments
