4 ms·

Yes, it's a question with a silly trick. Completely useless if one knows the answer, hard to spot if the person feigns struggle. Although, n•(n+1)/2 formula is

Yes, it's a question with a silly trick. Completely useless if one knows the answer, hard to spot if the person feigns struggle. Although, n•(n+1)/2 formula is not necessary. One can start with an xor sum and find the duplicate by xor adding elements again. This is another silly trick.

rocqua 4y ago
What is the closed form solution of the xor-sum though?
- jwilk 4y ago
  s(n) = • n if n mod 4 = 0, • 1 if n mod 4 = 1, • n + 1 if n mod 4 = 2, • 0 if n mod 4 = 3. Or alternatively: • s(4n) = 4n • s(4n + 1) = 1 • s(4n + 2) = 4n + 3 • s(4n + 3) = 0 Proof by induction: • s(4n + 1) = s(4n) ⊕ (4n + 1) = 4n ⊕ (4n + 1) = 1 • s(4n + 2) = s(4n + 1) ⊕ (4n + 2) = 1 ⊕ (4n + 2) = 4n + 3 • s(4n + 3) = s(4n + 2) ⊕ (4n + 3) = (4n + 3) ⊕ (4n + 3) = 0 • s(4n + 4) = s(4n + 3) ⊕ (4n + 4) = 0 ⊕ (4n + 4) = 4n + 4
- aliceryhl 4y ago
  You already have to spend the time to go through the list. Just add up the xor as you iterate through the list.
curiousgal 4y ago
Could also just use a hashtable, the keys are the array elements and the items are the occurrence of each element, then return the one with an occurrence of 2.
- 3np 4y ago
  Or just a hashset and return when about to insert an existing element.
Znafon 4y ago
That’s a very elegant solution. Hard looking problems that had simple, trick solutions were called Jewish Problems at the entrance of some universities. This would let the examiner fail a student for subjective reasons instead of academic success. The examiner would then be able to say « I failed them because of their skills, not because of their religions, look how easy the solution is ». Perhaps this is what we are reproducing as an industry with all our convoluted interview processes, and it may be a decorum to choose the candidates we want instead of using objective criteria.
- zx8080 4y ago
- sk0g 4y ago
  The explanation of the name somehow is a lot better than what I assumed it was referring to. The phrasing on the second sentence is... unfortunate.
  - Znafon 4y ago
    I’m referring to the easy looking, tricky to solve problems. I’ve heard them referred to by that term because they have been used at Moscow University to discriminate against Jewish students but I don’t know if they have other names. There is some discussions and examples of such problems at https://arxiv.org/pdf/1110.1556.pdf https://arxiv.org/pdf/1110.1556.pdf and http://3038.org/press/shen.pdf http://3038.org/press/shen.pdf.
    - sk0g 4y ago
      Of course, just the phrasing made me think the "trick solution" was eugenics, not a university admission trick. Unfortunately, historically "Jewish question" or "Jewish problem" has referred to these concerns [0]. Of course, following your first link it seems like the native phrase for it is in no way better, but that seems predictable as it's stemming from a racist premise in the first place. [0] https://en.wikipedia.org/wiki/Jewish_question https://en.wikipedia.org/wiki/Jewish_question

rocqua 4y ago

What is the closed form solution of the xor-sum though?

jwilk 4y ago
s(n) = • n if n mod 4 = 0, • 1 if n mod 4 = 1, • n + 1 if n mod 4 = 2, • 0 if n mod 4 = 3. Or alternatively: • s(4n) = 4n • s(4n + 1) = 1 • s(4n + 2) = 4n + 3 • s(4n + 3) = 0 Proof by induction: • s(4n + 1) = s(4n) ⊕ (4n + 1) = 4n ⊕ (4n + 1) = 1 • s(4n + 2) = s(4n + 1) ⊕ (4n + 2) = 1 ⊕ (4n + 2) = 4n + 3 • s(4n + 3) = s(4n + 2) ⊕ (4n + 3) = (4n + 3) ⊕ (4n + 3) = 0 • s(4n + 4) = s(4n + 3) ⊕ (4n + 4) = 0 ⊕ (4n + 4) = 4n + 4
aliceryhl 4y ago
You already have to spend the time to go through the list. Just add up the xor as you iterate through the list.

curiousgal 4y ago

Could also just use a hashtable, the keys are the array elements and the items are the occurrence of each element, then return the one with an occurrence of 2.

3np 4y ago
Or just a hashset and return when about to insert an existing element.

Znafon 4y ago

That’s a very elegant solution. Hard looking problems that had simple, trick solutions were called Jewish Problems at the entrance of some universities. This would let the examiner fail a student for subjective reasons instead of academic success. The examiner would then be able to say « I failed them because of their skills, not because of their religions, look how easy the solution is ». Perhaps this is what we are reproducing as an industry with all our convoluted interview processes, and it may be a decorum to choose the candidates we want instead of using objective criteria.

zx8080 4y ago
sk0g 4y ago
The explanation of the name somehow is a lot better than what I assumed it was referring to. The phrasing on the second sentence is... unfortunate.
- Znafon 4y ago
  I’m referring to the easy looking, tricky to solve problems. I’ve heard them referred to by that term because they have been used at Moscow University to discriminate against Jewish students but I don’t know if they have other names. There is some discussions and examples of such problems at https://arxiv.org/pdf/1110.1556.pdf https://arxiv.org/pdf/1110.1556.pdf and http://3038.org/press/shen.pdf http://3038.org/press/shen.pdf.
  - sk0g 4y ago
    Of course, just the phrasing made me think the "trick solution" was eugenics, not a university admission trick. Unfortunately, historically "Jewish question" or "Jewish problem" has referred to these concerns [0]. Of course, following your first link it seems like the native phrase for it is in no way better, but that seems predictable as it's stemming from a racist premise in the first place. [0] https://en.wikipedia.org/wiki/Jewish_question https://en.wikipedia.org/wiki/Jewish_question