Editorial

The specified sum can be computed using a loop. However, we will also derive the formula. Let $f (n) = 1^{2} + 2^{2} + 3^{2} + ... + n^{2}$ . Consider the sum:

k = 1 \sum n ((k + 1)^{3} - k^{3}) = (n + 1)^{3} - 1 = n^{3} + 3 n^{2} + 3 n

Expand the sum as follows:

k = 1 \sum n ((k + 1)^{3} - k^{3}) = k = 1 \sum n (3 k^{2} + 3 k + 1) = 3 k = 1 \sum n k^{2} + 3 k = 1 \sum n k + k = 1 \sum n 1 = 3 f (n) + 3 \cdot \frac{n + 1}{2} n + n

Then, equate the right-hand sides of both equations:

n^{3} + 3 n^{2} + 3 n = 3 f (n) + 3 (n + 1) n /2 + n, n^{3} + 3 n^{2} /2 + n /2 = 3 f (n), 2 n^{3} + 3 n^{2} + n = 6 f (n), f (n) = \frac{n}{6} (n + 1) (2 n + 1)

Algorithm realization

Implement the program using a loop.

scanf("%lld",&n);
for(i = 1; i <= n; i++)
  sum += i * i;
printf("%lld\n",sum);

Algorithm realization – formula

Implement the program using the formula.

scanf("%lld",&n);
sum = n * (n + 1) * (2 * n + 1) / 6;
printf("%lld\n",sum);

Java realization

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    long n = con.nextLong();
    long sum = n * (n + 1) * (2 * n + 1) / 6;
    System.out.println(sum);
    con.close();
  }
}

Python realization — formula

Implement the program using the formula.

n = int(input())
sum = n * (n + 1) * (2 * n + 1) // 6;
print(sum)

Python realization — loop

Implement the program using a loop.

n = int(input())
sum = 0
for i in range(1, n + 1):
  sum += i * i;
print(sum)