i forum mentioned given array of n
numbers:
arr[0........n-1]
the following conditon holds, ^
xor
operator `
f(l,r) = f(0,r) ^ f(0,l-1)
where f(l,r) = arr[l]^arr[l+1]^........arr[r]
i checked above taking number of arrays , different values of l
, r
, yes, true. don't understand how?
can please explain logic behind this?
use simplest property of xor
f(0,r) ^ f(0,l-1) = f(l,r) => (f(0,r) ^ f(0,l-1)) ^ f(0,l-1) = f(0,l-1) ^ f(l,r) => f(0,r) = f(l,r) ^ f(0,l-1) [since xor associative f(0,l-1) ^ f(0,l-1) = 0 , x ^ 0 = x] => f(0,r) = (arr[0]^...arr[l-1])^(arr[l]^...^arr[r])
which definition of f(0,r)
.
Comments
Post a Comment