4 ms·
> I would not have though to use this formula. The sum of the integers grows as the square of n so if n is anything but small you will overflow and get an erron
by Sesse__ 4y ago
> I would not have though to use this formula. The sum of the integers grows as the square of n so if n is anything but small you will overflow and get an erroneous answer.
As long as you can get wraparound semantics, the overflow is actually unproblematic. (n(n+1)/2 + k) mod 2^32 - (n(n+1)/2 mod 2^32) = k mod 2^32 = k.
- Znafon 4y agoIndeed, somehow this went completely over my head.
- jwilk 4y agoEven 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).
- ppsreejith 4y agoYou 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.
- Sesse__ 4y agoOr 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).
- deleted 4y ago[deleted]