Maximum XOR Using K Numbers from 1 to N in C++

In this problem, we are given two positive integers n and k. Our task is to find maximum xor between 1 to n using maximum X numbers

Let’s take an example to understand the problem,

Input − n = 5, k = 2

Output − 7

Explanation −

elements till 5 is 1, 2, 3, 4, 5
Selecting all XOR pairs:
1^2 = 3, 1^3 = 2, 1^4 = 5, 1^5 = 4
2^3 = 4, 2^4 = 6, 2^5 = 7
3^4 = 7, 3^5 = 6
4^5 = 1
The maximum here is 7.

To solve this problem, the maximum XOR can be found for any combination of numbers is found when all the bits of the number are set.

So, if the number is 5 its binary is 101, the maximum XOR will be 111 i.e. 7.

But if the number of elements to be taken for maximum XOR is 1 then the max XOR is 1. Else the maximum XOR will be found by making all bits set.

Example

Program to illustrate the working of our solution,

 Live Demo

#include <iostream>
using namespace std;
int maxXor(int n, int k) {
   if (k == 1)
      return n;
   int result = 1;
   while (result <= n)
      result <<= 1;
   return result - 1;
}
int main() {
   int n = 5, k = 2;
   cout<<"The maximum XOR of "<<k<<" numbers from 1 to"<<n<<" is "<<maxXor(n, k);
   return 0;
}

Output

The maximum XOR of 2 numbers from 1 to 5 is 7