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

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

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

    
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

1 Answer 1

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
    
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

This site is currently not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .