Say I have n positive numbers A1,A2...An
and Ak
is minimum among them. And d
is a number such that (A1-d) ⊕ (A2-d) ⊕ .......(An-1-d) ⊕ (An-d) = 0
where0<=d <= Ak
.
I want to know how many d are there . I know I can iterate all possible value of d and take XOR of n number every time and find out but complexity in this case is O(Ak∗n) which is O(n2) in worst case.
Is their any property of XOR which can help us to find number of d in less complexity than this ?
Edit :
Eq: If n=4
and numbers are = 4 6 8 10
then d
can be {0,3}
as 4 ⊕ 6 ⊕ 8 ⊕ 10 =0
and 1 ⊕ 3 ⊕ 5 ⊕ 7 =0