Didn't get this problem properly

#1

Can you please explain the approach with the help of code?

#2

Hello @anika203a you can solve this with the help of the Trie data structure :


if you have any doubt you can ask here:
Happy Learning!!

#3

I’ve seen this solution but I still did’nt get that

#4

@anika203a Have you seen that editorial for this?
prateek sir has made the editorial videos for this.
i think you should watch that first.

#5

Yeah I’ve seen that too

#6

@anika203a so what you have not understood in that?

#7

Basically I did’nt get this function:

int query(TrieNode *root, int pre_xor)

{

TrieNode *temp = root;

for ( int i=INT_SIZE-1; i>=0; i--)

{

// Find current bit in given prefix

bool val = pre_xor & (1<<i);

// Traverse Trie, first look for a

// prefix that has opposite bit

if (temp->arr[1-val]!=NULL)

temp = temp->arr[1-val];

// If there is no prefix with opposite

// bit, then look for same bit.

else if (temp->arr[val] != NULL)

temp = temp->arr[val];

}

return pre_xor^(temp->value);

}

#8

Can you explain this function?

#9

Hello @anika203a i think this will help you:
how algorihtm is working:

  1. Create an empty Trie. Every node of Trie is going to
    contain two children, for 0 and 1 value of bit.
  2. Initialize pre_xor = 0 and insert into the Trie.
  3. Initialize result = minus infinite
  4. Traverse the given array and do following for every
    array element arr[i].
    a) pre_xor = pre_xor ^ arr[i]
    pre_xor now contains xor of elements from
    arr[0] to arr[i].
    b) Query the maximum xor value ending with arr[i]
    from Trie.
    c) Update result if the value obtained in step
    4.b is more than current value of result.
#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.