Question

Google | OA Coding Questions and Solutions | Set - 15 | 2022 | SDE | India

Answer 1

Question asked : 

 

Answer 2

start with a dfs an from root and store dp[node][32]. where dp of node store the count of number bits. in that path from root to current node :
solution :
1. Use LCA to find the LCA of path u to v
find the number set bit at each position for each postion . number of set bit at i th position from LCA -> u and LCA -> v
we can get this by number bits set for ith bit at path u to LCA = dp[LCA][i] - (dp[u][i]);
similarly do this for LCA to v .
calculate the path length of LCA - > u and LCA to v  but storing their depth during dfs
2. Calculate the XOR from u to v = (LCA to u) xor (LCA to v)
            a. XOR from LCA to u:
                 
                iterate for all the 31 bits.
                       if for i th position.
                             if the number of set bit is odd then set the current bit
             b . following the process in step we will get XOR from path (LCA to u) use the similar process to find the number
3 . Calculate the AND from LCA to u and Lca to v and then (&) the result of both operation
         iterate for all 32 bits if the all number of set bits in ith position is equal to path then set that bit
4. Calculate fo OR from LCA to u
     iterate for all 32 bits. if number of set bits at ith postion is greater than 1 then set that bat

Complexity Analysis
  O(N * 32) for per computation of storing the depth and number of set bits at each position during dfs
  O(n Log(n)) for creating the sparse matrix for LCA
  O(log(n) * 32) for each query
P.S. Correct me. if I am wrong

Comments

awesome answer bro..

Answer 3

Code will be uploaded by 11th August 12pm.. by Kumar K..