 # Maximum xor sum

We have given an array A of size N . we can select any number X and perform XOR of all the elements of array with X . we have to select X in such a way that after performing the XOR operation , the sum of array is maximized . print the number X that you must select to maximize the sum of the array . if multiple X gives the same maximum sum , then print the minimum sum X

Constraints
1 <= N <= 10^4
1 <= A[i] <= 10^18
0 <= X < 2^63

sample input
5
10 12 5 7 19

output
9223372036854775800

this question asked in microsoft interview round

Nooo…not asked in microsoft interview round ,: )

output
9223372036854775800

Is this is the value of K

this is the value of X through which all elements are XORed and outputs in maximum sum

19 digits???

Yes 19 digits

given x is in range of 2 ^63

i think we need to use an array for bit frequency. I have implemented it but instead of gitting 9223372036854775800 i got 9223372036854775757. so if you want than i can give my ideas.

``````#include<bits/stdc++.h>

using namespace std;

typedef long long ull;

signed main(){
ull n; cin>>n;
ull a[n];
for(ull i = 0; i < n; i++) cin>>a[i];
ull x = {0};
for(ull i = 0; i < n; i++){
ull j = 62;
ull p = a[i];
while(p > 0){
if(p%2){
x[j]++;
}
j--;
p /= 2;
}
}

ull res = {0};
for(ull i = 0; i < 63; i++){
//cout<<x[i]<<" ";
if(x[i] <= n/2) res[i] = 1;
else res[i] = 0;
}
//cout<<"\n";
ull X = 0, mult = 1;
for(ull i = 62; i >= 0; i--){
//  cout<<res[i]<<" ";
if(res[i]) X += mult;
mult *= 2;
}
//cout<<"\n";
unsigned long long sum = 0;
for(ull i = 0; i < n; i++){
sum +=(1LL * (X ^ a[i]));
}
cout<<sum<<"\n";
return 0;
}``````
2 Likes

Duplicate of - Sum with xor

Lets keep it restricted to a single thread @vijju123 If possible merge these two threads.

Thank you.

No bro , i also mentioned above but it is different , Please don’t call vijju, he has also some other work.

I believe it can be solved with the same bit manipulation technique considering L = 1 and R = N, where N = size of the input array. Increasing the size of bit prefix array to 64 will do the work! Correct me if I’m wrong What makes you think that it is different from the other thread ? Any other approach ? @ssrivastava990

1 Like