I cheated on my Microsoft interview (2019)

Re:I cheated on my Microsoft interview (2019) by rocqua on Sunday June 05, 2022 @05:31AM (#31629347)

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

[ Parent | on HN ]

Re:I cheated on my Microsoft interview (2019) by aliceryhl on Sunday June 05, 2022 @07:25AM (#31629956)

You already have to spend the time to go through the list. Just add up the xor as you iterate through the list.

[ Parent | on HN ]

Re:I cheated on my Microsoft interview (2019) by jwilk on Sunday June 05, 2022 @06:34AM (#31629700)

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

[ Parent | on HN ]