Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

wolfSyntax's blog

Lowest Common Ancestor
By wolfSyntax, 10 years ago, In English

where root = 1, Left nodes (L) = 2n and Right nodes (R) = 2n+1. In getting the Common Ancestor, we need to compare the ancestor of Left nodes and Right Nodes until the result is the same or reaches to 1 as their common ancestor.

(1)
               /            \
              /              \
            (2)               (3)
         /       \         /       \
        /         \       /         \
      (4)         (5)   (6)         (7)

For example, The ancestor of : > 2 and 3 is 1. > 5 and 6 is 1. > 4 and 5 is 2. > 6 and 7 is 3. > and so on.

While(true): if(L > R) Then: L = L << 1; else if(R > L) Then: R = R << 1; else: break;

print(R)

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

there're faster algorithms.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Faster than log(max(L, R))? Can you tell the answer without looking at binary representation?

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I don't know if I got him right, but by saying that left child of n is 2n and right child of n is 2n+1, I assume he's talking about a full binary tree. In that case, the concept of LCA makes little sense, it will always be simply the longest common prefix in the binary representation of the two nodes, which is what his function would return.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Now way :))

→ Reply