6
$\begingroup$

There is a classic problem of finding the only number that occurs an odd number of times in a list. The solution is to xor everything and the result is the requested number.

The key properties used here are the involution of xor (i.e. a number's inverse is the same number) and the closure over integer range of the variable.

Now, are there any other operations that could be used for this? I could only find 1/x which, unfortunately, cannot be used due to precision erros.

$\endgroup$
  • $\begingroup$ How would you use 1/x for non-zero rational numbers? ​ (They avoid the precision errors.) ​ ​ ​ ​ $\endgroup$ – user12859 Feb 3 '17 at 13:22
  • 1
    $\begingroup$ The question is equivalent to asking a description of all automorphism on Boolean group of each size. $\endgroup$ – Apiwat Chantawibul Feb 3 '17 at 13:31
  • $\begingroup$ @RickyDemer Multiply all the inverses in the list. The inverse of the result is what you are looking for, but this is very hard to implement in practice since you have to deal either with performing the divisions (thus rounding errors) or with simplifications (thus not very effificent). $\endgroup$ – Paul92 Feb 3 '17 at 14:35
  • 1
    $\begingroup$ When your list is [1/2,1/2,1/2], multiplying "all the inverses in the list" gives either 1/8 or 8 depending on what you mean by that. ​ ​ ​ The inverses of ​ 1/8 , 8 ​ are ​ 8 , 1/8 ​ respectively, but neither of those is 1/2, which is "the only number that occurs an odd number of times in" [1/2,1/2,1/2]. ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Feb 3 '17 at 14:43
7
$\begingroup$

Roll your own.

Take an arbitrary bijection $f$ from the integers to integers. This is a permutation of the integers.

Then, take the conjugate of XOR ($\oplus$): $$ g(x,y) = f^{-1}(f(x) \oplus f(y)) $$ We then have $$ g(x,x) = f^{-1}(0) $$ which now acts as the "new zero" (neutral element) $$ g(x,f^{-1}(0)) = x $$ We also have that $g$ is associative and commutative $$ g(x,y) = g(y,z) \qquad g(g(x,y),z) = g(x,g(y,z)) $$ So, we still have an abelian group where $x^{-1}=x$. The trick on arrays mentioned by the OP still works.

$\endgroup$
  • $\begingroup$ Thanks for your recent tag cleanups but there's no need to change tags on closed questions. Those get deleted anyway, so it doesn't really matter if they have the wrong tags. (And, in general, editing closed questions automatically nominates them for reopening, but I'm not sure that actually applies to tag-only edits.) $\endgroup$ – David Richerby Mar 6 '17 at 0:19
  • 1
    $\begingroup$ @DavidRicherby Interesting, thank you. I was browsing a few specific tags and I found non-relevant questions, so I actually wondered if I should retag them, before deciding to do so. In the future, I'll limit that activity to the still-open questions. $\endgroup$ – chi Mar 6 '17 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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