Maximum xor sum

1

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

2

Nooo…not asked in microsoft interview round ,: )

3

asked in microsoft test

4
5

output
9223372036854775800

Is this is the value of K

6

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

7

19 digits???

8

Yes 19 digits

9

given x is in range of 2 ^63

10

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;
}
11
2 Likes
12

Duplicate of - Sum with xor - #20 by guitarlover

Lets keep it restricted to a single thread :slight_smile:

@vijju123 If possible merge these two threads.

Thank you.

13

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

14

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! :slight_smile:

Correct me if I’m wrong :slight_smile:

What makes you think that it is different from the other thread ? Any other approach ? @ssrivastava990

1 Like