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
Please Help
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
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[63] = {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[63] = {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;
}
Duplicate of - Sum with xor - #20 by guitarlover
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