Menu
I a forum it is mentioned that given array of n numbers:
arr[0........n-1]
The following conditon holds, ^ is the 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 the above taking number of arrays and different values of l and r and YES, it is true. But I don't understand how?
Can somebody please explain the logic behind this?
576
Important properties of XOR This is clear from the definition of XOR: it doesn't matter which way round you order the two inputs. Associative : A ⊕ ( B ⊕ C ) = ( A ⊕ B ) ⊕ C. This means that XOR operations can be chained together and the order doesn't matter.
The XOR logical operation, exclusive or, takes two boolean operands and returns true if, and only if, the operands are different. Conversely, it returns false if the two operands have the same value.
A connective in logic known as the "exclusive or," or exclusive disjunction. It yields true if exactly one (but not both) of two conditions is true. The XOR operation does not have a standard symbol, but is sometimes denoted (this work) or.
Use the 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 is associative f(0,l-1) ^ f(0,l-1) = 0 and x ^ 0 = x]
=> f(0,r) = (arr[0]^...arr[l-1])^(arr[l]^...^arr[r])
which is definition of f(0,r).
164
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
