Problem statement:

Given an array of n elements and an integer k, find an integer x in the range [0,k] such that Xor-sum(x) is maximized. Print the maximum value of the equation.

Xor-sum(x)=(x XOR A[1]) (x XOR A[2]) (x XOR A[3]) ………….. (x XOR A[N])

Input Format

The first line contains integer N denoting the number of elements in A. The next line contains an integer, k, denoting the maximum value of x. Each line i of the N subsequent lines(where 0<=i<=N) contains an integer describing Ai.

Constraints

1<=n<=10^5
0<=k<=10^9
0<=A[i]<=10^9

Sample Input

3
7
1
6
3

Sample Output

14

Explanation

Xor_sum(4)=(4^1) (4^6) (4^3)=14.

This problem was asked in Infosys requirement test. I was going through previous year papers & I came across this problem. I was only able to come up with a brute-force solution which is just to calculate the equation for every x in the range [0,k] and print the maximum. But, the solution won't work for the given constraints.

My solution

#include <bits/stdc  .h>
using namespace std;
int main()
{
  int n, k, ans = 0;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i  ) cin >> a[i];
  for (int i = 0; i <= k; i  ) {
    int temp = 0;
    for (int j = 0; j < n; j  ) {
      temp  = (i ^ a[j]);
    }
    ans = max(temp, ans);
  }
  cout << ans;
  return 0;
}

CodePudding user response：

As said in other comments each bit of x will give an independent contribution to the sum, so the first step is to calculate the added value for each possible bit.

To do this for the i-th bit of x count the number of 0s and 1s in the same position of each number in the array, if the difference N0 - N1 is positive then the added value is also positive and equal to (N0-N1) * 2^i, let's call such bits "useful".

The number x will be a combination of useful bits only.

Since k is not in the form 2^n - 1, we need a strategy to find the best combination (if you don't want to use brute force on the k possible values).

Consider then the binary representation of k and loop over its bits starting from the MSB, initializing two variables: CAV (current added value) = 0, BAV (best added value) = 0.

If the current bit is 0 loop over.

If the current bit is 1:

a) calculate the AV sum of all useful bits with lower index plus the CAV, if the result is greater then the BAV then replace BAV

b) if the current bit is not useful quit loop

c) add the current bit added value to CAV

When the loop is over, if CAV is greater than BAV replace BAV

CodePudding user response：

The trick here is that XOR works on bits in parallel, independently. You can optimize each bit of x. Brute-forcing this takes 2*32 tries, given the constraints.

CodePudding user response：

I think you can consider solving for each bit. The number X should be the one that can turn on many high-order bits in the array. So you can count the number of bits 1 for 2^0, 2^1, ... And for each position in the 32 bits consider turning on the ones that many number has that position to be bit 0.

Combining this with the limit K should give you an answer that runs in O(log K) time.