I think they meant that XOR avoids the overflow risk, whereas doing the sum of the array to figure out which number could cause an overflow.

(wrapping) overflow doesn't affect the final result.

You can also calculate the XOR-accumulation of all values between 1 and n in O(1) using a lookup table like this:

    [n, 1, n+1, 0][n%4]

Well there you go, I learnt something today. My spidey sense told me to be wary of overflow but I suppose I was wrong

> The trick works on any Abelian group

(https://en.wikipedia.org/wiki/Abelian_group -- I'll use ⋆ as the Abelian group's operation, and ~ for inversion, below.)

I believe you are implying:

(g(1) ⋆ ... ⋆ g(n)) ⋆ ~(g(i(1)) ⋆ g(i(2)) ⋆ ... ⋆ g(i(n-1))) = g(m)

where "m" is the group element index that is not covered by "i".

However, for this to work, it is requried that you can distribute the inversion ~ over the group operation ⋆, like this:

~(g(i(1)) ⋆ g(i(2)) ⋆ ... ⋆ g(i(n-1))) = ~g(i(1)) ⋆ ~g(i(2)) ⋆ ... ⋆ ~g(i(n-1))

because it is only after this step (i.e., after the distribution) that you can exploit the associativity and commutativity of operation ⋆, and reorder the elements in

g(1) ⋆ ... ⋆ g(n) ⋆ ~g(i(1)) ⋆ ~g(i(2)) ⋆ ... ⋆ ~g(i(n-1))

such that they pairwise cancel out, and leave only the "unmatched" (missing) element -- g(m).

However, where is it stated that inversion ~ can be distributed over group operation ⋆? The above wikipedia article does not spell that out as an axiom.

Wikipedia does mention "antidistributivity":

https://en.wikipedia.org/wiki/Distributive_property#Antidist...

(which does imply the distributivity in question here, once we restore commutativity); however, WP says this property is indeed used as an axiom ("in the more general context of a semigroup with involution"). So why is it not spelled out as one for Abelian groups?

... Does distributivity of inversion ~ over operation ⋆ follow from the other Abelian group axioms / properties? If so, how?

> ... Does distributivity of inversion ~ over operation ⋆ follow from the other Abelian group axioms / properties? If so, how?

It does. For all x and y:

  (1) ~x ⋆ x = 0 (definition of the inverse)
  (2) ~y ⋆ y = 0 (definition of the inverse)
  (3) (~x ⋆ x) ⋆ (~y ⋆ y) = 0 ⋆ 0 = 0 (from (1) and (2))
  (4) (~x ⋆ ~y) ⋆ (x ⋆ y) = 0 (via associativity and commutativity)

In (4) we see that (~x ⋆ ~y) is the inverse of (x ⋆ y). That is to say, ~(x ⋆ y) = (~x ⋆ ~y). QED.

Right. Another way to see this is that for a general (possibly non-Abelian) group, the inverse of xy is y⁻¹x⁻¹ (because xyy⁻¹x⁻¹ = x1x⁻¹ = xx⁻¹ = 1 [using "1" for the identity here, as is typical for general groups], or more colloquially, "the inverse operation of putting on your socks and shoes is taking off your shoes and socks"). For an Abelian group, y⁻¹x⁻¹ = x⁻¹y⁻¹, and we're done.

Awesome, thanks! :)