You can figure out the possible values of d
one bit at a time. Consider the equation mod 2:
(A1-d) ⊕ (A2-d) ⊕ .......(A{n-1}-d) ⊕ (An-d) = 0 mod 2
Try 0 and 1 for d
, see if either works. Say d==1 is the only assignment that works. Then try the values 1 and 3 in the equation:
(A1-d) ⊕ (A2-d) ⊕ .......(A{n-1}-d) ⊕ (An-d) = 0 mod 4
and so on, taking all valid d
s mod 2^i
and trying both d
and d+2^i
mod 2^{i+1}
. The reason why this works is that both subtraction and xor do not propagate any information from higher bits to lower bits, so if you find a solution to the mod 2 equation, it remains a solution no matter what the higher-order bits of d
are set to.
The running time should be something like O(n * log Ak * #of solutions).
Example:
A = {9,12,23,30} try d=0,1 mod 2. Both work. try d=0,1,2,3 mod 4. All work. try d=[0-7] mod 8. 1,3,5,7 work. try d=[1,9,3,5,7] mod 16. 3,7 work. (no need to check if d>Ak) now we've tried up to Ak, check the remaining solutions for the remaining high-order bits. 3 and 7 work.
Example:
A = {4,6,8,10} try d=0,1 mod 2. Both work. try d=0,1,2,3 mod 4. All work. try d=0,4,1,2,3 mod 8. All work. at this point you've tried all d up to Ak. Do a final check and 0,3,4 work.