8
$\begingroup$

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

  • 0
    So is this bitwise XOR? If so, you can do this in `O(n)` by shifting and bitwise AND-ing.2012-10-22
  • 0
    The xor is commutative, associative and self-inverse.2012-10-22
  • 0
    @H2CO3 2 XOR 3 = 1 and 1 XOR 2 = 32012-10-22
  • 0
    @H2CO3 I cannot see how2012-10-22
  • 0
    @JanDvorak yeah , I know these properties but I couldn't understand how I can use them to solve this problem , can u elaborate please.2012-10-22
  • 0
    @sheldon So yes, **this is called bitwise XOR.**2012-10-22
  • 0
    @sheldon also, finding all possible values of `d` is the question then?2012-10-22
  • 0
    Oh, the question is "how many d are there", not "find a d such that"2012-10-22
  • 0
    No, if that doesn't effect the complexity then it is added excellence, but I don't this that would be possible .2012-10-22
  • 0
    Because it is a subtraction there is probably no mathematical shortcut. It will depend on the unique characteristics of the numbers.2012-10-22
  • 0
    @TylerDurden Numbers are random . Here subtraction is uniform , so it might be possible to do it in less complexity like O( n logn).2012-10-22
  • 0
    @H2CO3 Please notify me when you're done writing the answer. I have some ideas that could get me to `O(n*log(a_k))` but nothing complete.2012-10-22
  • 0
    @JanDvorak Feel free to write an answer, I seemingly misunderstood what the question was.2012-10-22
  • 1
    Looks similar to http://stackoverflow.com/questions/12655593/minimum-sum-required-to-make-xor-of-some-integers-to-zero (yes I know they are completely different questions).2012-10-22
  • 0
    @Barmar I initially asked there only and thought posting here might make discussion more effective .2012-10-22
  • 0
    I think as we are doing uniform subtraction so XOR of entire sequence can take only limited values (I checked for several random values and observed repeated result of XOR for different value of d), that might help somehow to find solution.2012-10-22
  • 0
    well... if an odd number of As is odd, and an odd number of As is even, there are no solutions. If there is an odd number of odd numbers and an even number of even numbers, D must be odd. My gut's telling me iff n is odd, there is always exactly one D (its parity _is_ given). A naive extrapolation would be that iff n divides 2^x then 2^x divides the number of solutions.2012-10-22
  • 0
    IF log(n)/log(2) is integer AND all As are mutually equal, THEN any D in the given range will work.2012-10-22
  • 0
    In general, if there are duplicated entries, then pairs of such entries may be removed without affecting the result (except by setting a lower range), so one can assume the entries are distinct.2012-10-22
  • 0
    IF n is odd THEN there exists a unique d such that the statement is true. The d might not be lower than Ak. The lowest bit of d is the xor of all lowest bits of A1..An. Each later bit of d is the xor of all corresponding bits of A1..An and all borrows from the previous bit. You can calculate all bits of XOR(A1..An) in parallel, so IF n is odd, THEN d is unique and can be found in O(n+log(Am)) where Am is the maximum of A1..An.2012-10-22
  • 0
    I think that IF n is even, THEN d is not unique (and may not exist).2012-10-22
  • 0
    for even n: IF an odd number of A1..An is odd, THEN d does not exist. The same rule applies to higher bits also, and each bit forces the xor of borrows from the lower bit (which may set a constraint on d). Elaborating the number of such constraints should reveal the answer to the unbounded counting problem (which is an upper bound to the original, bounded counting problem).2012-10-22
  • 0
    note that the bounded enumeration performance is limited by the number of d's.2012-10-22

1 Answers 1