5 ms·
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
by ppsreejith 4y ago
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.
- 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).