PROBLEM LINK:
Author: Rahul Johari
Tester: Rahul Johari
DIFFICULTY:
EASY-MEDIUM, MATHS
PREREQUISITES:
Division, Summation of series, modular operation
PROBLEM:
Given a number N and another number MOD, you have to calculate the sum of numbers from 1 to N as:
for ( i=1;i<=N;i++ )
sum += i % MOD;
EXPLANATION:
By the division algorithm, let N = qm+r with 0 ≤ r < m. Consider the sequence
(1 m),(2 m), …,(N % m). It looks like this:
1, 2, 3, ..., m − 1, 0,
1, 2, 3, ..., m − 1, 0,
...
1, 2, 3, ..., m − 1, 0,
1, 2, 3, ..., r
There are q layers, each with m elements and a final layer with r elements.
We know that sum of first N terms is N(N+1)/2 therefore the sum the numbers in
each of the q layers is m(m−1)/2 and the sum of the numbers in the last layer is r(r+1)/2.
Therefore using this you can easily calculate sum of large values of N also is O(1) complexity.
AUTHOR’S AND TESTER’S SOLUTIONS:
Solution can be found here.