I cheated on my Microsoft interview (2019)

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

Even with wraparound semantics, you can't compute n(n+1)/2 naively, because (n(n+1) mod N) / 2 ≠ n(n+1)/2 mod N.

So actually not knowing the formula is kinda advantageous, because computing the sum as 1 + 2 + … + n (with every addition mod N) gives you the right answer (mod N).

[ Parent | on HN ]

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

You could delay division by 2 until the end. I.e ((2 * S mod N - n*(n+1) mod N) mod N) / 2

Where S is the sum of the array achieved through iterative addition with every addition mod N and N > 2n.

[ Parent | on HN ]

Re:I cheated on my Microsoft interview (2019) by Sesse__ on Sunday June 05, 2022 @08:50AM (#31630523)

Or you can assume N is less than 2^31, and clear out the top bit in the final answer (because that's the only place the wrong values can come from). Which is admittedly pretty hackish, but…

Edit: The simplest solution is probably just doing (n/2)*(n+1) (assuming n is even; move the division for n odd).

[ Parent | on HN ]