MAX XOR PAIR. . . . . . . . .

#1

Bhaiya iski time or space complexity explain krdo?

#2

hello @CODER_JATIN

ok , pehle space complexity ka dekhte hai
oth level be 1 hi node hoga right (root node)
1st level pe 2 node honge (0 aur 1 , 2^1)
2nd level pe 4 node honge ( 0 ke 2 aur 1 ke do 2^2)
…
n-1 th level be 2^(n-1) node honge
nth level pe 2^n node honge (basically jitne node n-1 th level be honge uske double)
to space complexity jo hogi trie ki wo
1 + 2 + 2^2 + 2^3 … 2^n
yaha pe n ki maximum value 31-32 hogi
to space complexity trie ki O( 1 + 2+2^2 + …2^31) ya to isko solve kar lo
ya O(2^31) boldo worst case me.
ss
abhi itna smajh aayha ho to batawo phir aage batata hun

#3

Hanji bhaiya samjh gya worst case mai o(2^N) hogi ,okay!!!

#4

yaha n jo hai wo maximum number of bits hai, ye dhyan rakhna

#5

hanji bhaiya longest tree (31) height ka hi bnega na?

#6

bhaiya time complexity bhi explain krdo pls

#7

ha … …

#8

pehle tum ye batao ki insertion kitna time lega trie me

#9

trie mai insertion ke liye time lgega o(n) , and n=31 hoga ,??

#10

ha …

to agar N elements hai total, to time kitna lagega
N * n (n is maximum number of bits ,N is number of elements in array)

#11

aur max_xor helper bhi o(n) lega to final cmplexity

O(N* 2n)->O(N* n)->O(31* N) -> O(N)

#12

okay bhaiya , yr bhaiya merko complexities m hamesha doubt rehta hai , kya kru fir?

#13

https://ide.codingblocks.com/s/443596 , chk karna bhaiya ?

#14

Thode practice karo , ye kaafi important chiz hai

#15

Check karna https://ide.codingblocks.com/s/443600

#16

Okay bhaiya !!, Thank you :slight_smile:

#17

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.