Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 =0and 1 ⊕ 3 ⊕ 5 ⊕ 7 =0

share|improve this question
    
So is this bitwise XOR? If so, you can do this in O(n) by shifting and bitwise AND-ing. –  H2CO3 Oct 22 '12 at 17:45
    
The xor is commutative, associative and self-inverse. –  Jan Dvorak Oct 22 '12 at 17:45
    
@H2CO3 2 XOR 3 = 1 and 1 XOR 2 = 3 –  tesla Oct 22 '12 at 17:48
    
@H2CO3 I cannot see how –  Jan Dvorak Oct 22 '12 at 17:48
1  
Looks similar to stackoverflow.com/questions/12655593/… (yes I know they are completely different questions). –  KennyTM Oct 22 '12 at 18:13
show 18 more comments

migrated from stackoverflow.com Oct 22 '12 at 22:07

This question came from our site for professional and enthusiast programmers.

1 Answer

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 ds 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.
share|improve this answer
    
The original problem is a counting problem. I was hoping for an output-insensitive algorithm. Still, this might be the optimal algorithm for enumeration. +1 –  Jan Dvorak Oct 22 '12 at 19:20
    
The time complexity is not O(log Ak * #d), more like O(log Ak * #d * n) - you have to include the time needed to calculate the XORs. You might be able to reach O(log Ak * #d + n). –  Jan Dvorak Oct 22 '12 at 19:25
    
True, there's an n in there also, I'll add it. –  Keith Randall Oct 22 '12 at 19:26
1  
I also conjencture it is possible to reach O(log Ak + #d + n) by finding one solution and generating each next solution in constant time. –  Jan Dvorak Oct 22 '12 at 19:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.