# Java Program for Sum of squares of first n natural numbers

Given a positive integer **N**. The task is to find 1^{2} + 2^{2} + 3^{2} + ….. + N^{2}.

Examples:

Input : N = 4 Output : 30 1^{2}+ 2^{2}+ 3^{2}+ 4^{2}= 1 + 4 + 9 + 16 = 30 Iput : N = 5 Output : 55

**Method 1: O(N)** The idea is to run a loop from 1 to n and for each i, 1 <= i <= n, find i^{2} to sum.

`// Java Program to find sum of` `// square of first n natural numbers` `import` `java.io.*;` ` ` `class` `GFG {` ` ` ` ` `// Return the sum of square of first n natural numbers` ` ` `static` `int` `squaresum(` `int` `n)` ` ` `{` ` ` `// Iterate i from 1 and n` ` ` `// finding square of i and add to sum.` ` ` `int` `sum = ` `0` `;` ` ` `for` `(` `int` `i = ` `1` `; i <= n; i++)` ` ` `sum += (i * i);` ` ` `return` `sum;` ` ` `}` ` ` ` ` `// Driven Program` ` ` `public` `static` `void` `main(String args[]) ` `throws` `IOException` ` ` `{` ` ` `int` `n = ` `4` `;` ` ` `System.out.println(squaresum(n));` ` ` `}` `}` ` ` `/*This code is contributed by Nikita Tiwari.*/` |

**Output:**

30

**Method 2: O(1)**

Proof:

We know, (k + 1)^{3}= k^{3}+ 3 * k^{2}+ 3 * k + 1 We can write the above identity for k from 1 to n: 2^{3}= 1^{3}+ 3 * 1^{2}+ 3 * 1 + 1 ......... (1) 3^{3}= 2^{3}+ 3 * 2^{2}+ 3 * 2 + 1 ......... (2) 4^{3}= 3^{3}+ 3 * 3^{2}+ 3 * 3 + 1 ......... (3) 5^{3}= 4^{3}+ 3 * 4^{2}+ 3 * 4 + 1 ......... (4) ... n^{3}= (n - 1)^{3}+ 3 * (n - 1)^{2}+ 3 * (n - 1) + 1 ......... (n - 1) (n + 1)^{3}= n^{3}+ 3 * n^{2}+ 3 * n + 1 ......... (n) Putting equation (n - 1) in equation n, (n + 1)^{3}= (n - 1)^{3}+ 3 * (n - 1)^{2}+ 3 * (n - 1) + 1 + 3 * n^{2}+ 3 * n + 1 = (n - 1)^{3}+ 3 * (n^{2}+ (n - 1)^{2}) + 3 * ( n + (n - 1) ) + 1 + 1 By putting all equation, we get (n + 1)^{3}= 1^{3}+ 3 * Σ k^{2}+ 3 * Σ k + Σ 1 n^{3}+ 3 * n^{2}+ 3 * n + 1 = 1 + 3 * Σ k^{2}+ 3 * (n * (n + 1))/2 + n n^{3}+ 3 * n^{2}+ 3 * n = 3 * Σ k^{2}+ 3 * (n * (n + 1))/2 + n n^{3}+ 3 * n^{2}+ 2 * n - 3 * (n * (n + 1))/2 = 3 * Σ k^{2}n * (n^{2}+ 3 * n + 2) - 3 * (n * (n + 1))/2 = 3 * Σ k^{2}n * (n + 1) * (n + 2) - 3 * (n * (n + 1))/2 = 3 * Σ k^{2}n * (n + 1) * (n + 2 - 3/2) = 3 * Σ k^{2}n * (n + 1) * (2 * n + 1)/2 = 3 * Σ k^{2}n * (n + 1) * (2 * n + 1)/6 = Σ k^{2}

`// Java Program to find sum` `// of square of first n` `// natural numbers` `import` `java.io.*;` ` ` `class` `GFG {` ` ` ` ` `// Return the sum of square` ` ` `// of first n natural numbers` ` ` `static` `int` `squaresum(` `int` `n)` ` ` `{` ` ` `return` `(n * (n + ` `1` `) * (` `2` `* n + ` `1` `)) / ` `6` `;` ` ` `}` ` ` ` ` `// Driven Program` ` ` `public` `static` `void` `main(String args[])` ` ` `throws` `IOException` ` ` `{` ` ` `int` `n = ` `4` `;` ` ` `System.out.println(squaresum(n));` ` ` `}` `}` ` ` `/*This code si contributed by Nikita Tiwari.*/` |

**Output:**

30

**Avoiding early overflow:**

For large n, the value of (n * (n + 1) * (2 * n + 1)) would overflow. We can avoid overflow up to some extent using the fact that n*(n+1) must be divisible by 2.

`// Java Program to find sum of square of first` `// n natural numbers. This program avoids` `// overflow upto some extent for large value` `// of n.` ` ` `import` `java.io.*;` `import` `java.util.*;` ` ` `class` `GFG {` ` ` `// Return the sum of square of first n natural` ` ` `// numbers` ` ` `public` `static` `int` `squaresum(` `int` `n)` ` ` `{` ` ` `return` `(n * (n + ` `1` `) / ` `2` `) * (` `2` `* n + ` `1` `) / ` `3` `;` ` ` `}` ` ` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `n = ` `4` `;` ` ` `System.out.println(squaresum(n));` ` ` `}` `}` ` ` `// Code Contributed by Mohit Gupta_OMG <(0_o)>` |

**Output:**

30

Please refer complete article on Sum of squares of first n natural numbers for more details!