Max_xor_subarray

#1

curr_xor += pow(2,i) should be in line 46 than line 42. Because if root->left doesnot exist, then it will settle for root->right and root->right will be contributing in curr_xor

#2

@swatiguptasg
Yes you’re right
But what is your query here ?

#3

It is giving the wrong output for maximum xor subarray question if we put curr_xor +=pow(2,i) in line 46 rather than line 42.

#4

@swatiguptasg
You forgot to add insert(root,0) before iterating array values
Do that and see

#5

I have created root=newnode(), in line 54

#6

@swatiguptasg
That’s fine
But you also need to add 0 before start putting elements in the trie
do insert(root,0) before the insert(root,arr[i]) for loop

#7

Can u explain why we need to insert(root,0). Even after insert(root,0) at line 64 it is giving wrong output.

#8

@swatiguptasg
I just tried and it worked
You might have forgotten to correct line 42 and 46
Do that as well

#9

output should be 7 but it is giving 3

#10

@swatiguptasg
I just checked myself
It gave 7
Make sure you do all 3
insert(root,0)
Comment line 46
Uncomment line 42

#11

my doubt was we should comment line 42 and uncomment line 46.

#12

@swatiguptasg
I got your query wrong then
Sorry for that
And no you’re not correct
As you can see a XOR adds a power of 2 to the ans only if a bit is 0 in a number and 1 in another
So as you can see when current bit was 0 you added pow(2,i) when you went to the right because right represented 1 and 1^0 is 1
Similar logic can be extended to bit 1 in current number
So Line 42 should have that and not line 46

1 Like