Xor sum 1 PROBLM

#1

I CAN GO TO ALL POSSIBLE NUMBERS AND TAKE XOR I.E BASICALLY BRUTEFORCE
BUT THEN IN THAT THE TIME COMPLEXITY WILL BE VERY POOR
PLEASE TELL ME WHAT LOGIC SHOULD I APPLY HERE
I MEAN IS THERE ANY SHORTCUT OR JUST
BRUTEFORCE SOLVING (ITERATING TO COVER EVERY POSSIBILITY

#2

Please add the problem link.

#3

sry i forgot
:sweat_smile:

https://hack.codingblocks.com/contests/c/512/562

#4

Answer will depend only on how the maximum value of array changes its value.
And maximum value can go from (0 to 2* max )value as mentioned in question
so just let say x = xor the remaining values(other than maximum) and find the maximum xor between this x and (0 to 2 *max ) and resultant would be the answer .
Reason : maximum answer will be from maximum value as final answer should have high degree of set bits of maximum no

#5

The maximum number of bits you can get is by the maximum number present in the array.
Now for this,take out the xor sum of rest of the elements and try to figure out which number will give the maximum xor sum with the remaining xor sum.
Keeping in mind the bits must be opposite in nature to get maximum value as 1 xor 0=1
or 0 xor 1=1 so the set bits will give you the maximum possible number and also the range of number can be from (0 ,2*maximum element) only.

#6

maine bhi yahi likha h bhai :stuck_out_tongue:

#7

Also you can implement this question using bitwise operators.
But for your simplification I have solved it using vectors only.
Code link:https://ide.codingblocks.com/s/42688

#8

@Anubhav-Aron-1353657
I was just trying to explain how to find the value that gives maximum xor in the range 0 to 2*max, because brute force will give complexity of 2 x 10^9. We have to use bitwise operator and defination of xor for that purpose, which was missing in your explanation maybe.

1 Like
#9

I did it so that student can optimize it and not giving the exact answer to him so that he could analyze the approach and giving him exact working code before he even tried it is just a waste of a beautiful problem

#10

dont worry i wont / dont do copy and paste or see the code until and unless i give my best and thanks a lot bhaiya, i got the logic,i will try to code and will ask if any problm arises😄

2 Likes