we have given with an array of coordinate pairs in the form of (x,y) and an integer k, we have to find the number of pairs such that ((x1^x2)+(y1^y2))=k where (x1,y1) is first pair and (x2,y2) is second pair... also i<j, assume the length of the input array to be 10^5 and k can go up to 100..
i know it's some kind of map question where we have separate the relationship in form of x1,y1 and x2,y2 independently...but not able to come up with such relationship... can someone help me with some good approaches and also the intuition behind it... thank you!!
Notice that $$$k$$$ is very small. Let's assume that all coordinates lie in range $$$[0,2^{60})$$$ For a fixed $$$(x_1,y_1)$$$, Notice that only those pairs $$$(x_2,y_2)$$$ are relevant in which $$$x_2$$$ and $$$x_1$$$ has same prefix of length at least $$$54$$$. This is because if any bit at index $$$>6$$$ (bits are $$$0$$$ indexed from left to right) differs in $$$x_1$$$ and $$$x_2$$$, then $$$x_1 ^ x_2 > 100 $$$. This reduces the number of valid $$$x_2$$$ for a fixed $$$x_1$$$ to be only around $$$128$$$. Now, can you solve further ?
So we try for all possibility of 6 bits with that prefix and check if such x2 exist that satisfy the condition? So some kind of trie or map implementation ?
Yes, for a fixed possibility of $$$x_2$$$, you can store the freq of the corresponding $$$y_2$$$ in a map.
Great approach, Thank you for a great explanation, really appreciate that...