Sum of squares of first n natural numbers

0 0 9 minutes read

Given a positive integer N. The task is to find 1² + 2² + 3² + ….. + N².

Examples :

Input : N = 4
Output : 30
1² + 2² + 3² + 4²
= 1 + 4 + 9 + 16
= 30

Input : 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² to sum.

Below is the implementation of this approach

C++

// CPP Program to find sum of square of first n natural numbers
#include <bits/stdc++.h>
using namespace std;
 
// Return the sum of square of first n natural numbers
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
int main()
{
    int n = 4;
    cout << squaresum(n) << endl;
    return 0;
}

Java

// 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.*/

Python3

# Python3 Program to
# find sum of square
# of first n natural 
# numbers
 
 
# Return the sum of
# square of first n
# natural numbers
def squaresum(n) :
 
    # Iterate i from 1 
    # and n finding 
    # square of i and
    # add to sum.
    sm = 0
    for i in range(1, n+1) :
        sm = sm + (i * i)
     
    return sm
 
# Driven Program
n = 4
print(squaresum(n))
 
# This code is contributed by Nikita Tiwari.*/

C#

// C# Program to find sum of
// square of first n natural numbers
using System;
 
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()
    {
        int n = 4;
         
        Console.WriteLine(squaresum(n));
    }
}
 
/* This code is contributed by vt_m.*/

PHP

<?php
// PHP Program to find sum of 
// square of first n natural numbers
 
// Return the sum of square of
// first n natural numbers
function squaresum($n)
{
    // Iterate i from 1 and n
    // finding square of i and 
    // add to sum.
    $sum = 0;
    for ($i = 1; $i <= $n; $i++)
        $sum += ($i * $i);
    return $sum;
}
 
// Driven Code
$n = 4;
echo(squaresum($n));
 
// This code is contributed by Ajit.
?>

Javascript

<script>
 
// Javascript Program to find sum of square of first n natural numbers
 
// Return the sum of square of first n natural numbers
function squaresum(n)
{
    // Iterate i from 1 and n
    // finding square of i and add to sum.
    let sum = 0;
    for (let i = 1; i <= n; i++)
        sum += (i * i);
    return sum;
}
 
// Driven Program
 
    let n = 4;
    document.write(squaresum(n) + "<br>");
 
// This code is contributed by Mayank Tyagi
 
</script>

Output :

Time Complexity: O(n)

Auxiliary Space: O(1)

Method 2: O(1)

Sum of squares of first N natural numbers = (N*(N+1)*(2*N+1))/6

For example
For N=4, Sum = ( 4 * ( 4 + 1 ) * ( 2 * 4 + 1 ) ) / 6
= 180 / 6
= 30
For N=5, Sum = ( 5 * ( 5 + 1 ) * ( 2 * 5 + 1 ) ) / 6
= 55

Proof:

We know,
(k + 1)³ = k³ + 3 * k² + 3 * k + 1
We can write the above identity for k from 1 to n:
2³ = 1³ + 3 * 1² + 3 * 1 + 1 ......... (1)
3³ = 2³ + 3 * 2² + 3 * 2 + 1 ......... (2)
4³ = 3³ + 3 * 3² + 3 * 3 + 1 ......... (3)
5³ = 4³ + 3 * 4² + 3 * 4 + 1 ......... (4)
...
n³ = (n - 1)³ + 3 * (n - 1)² + 3 * (n - 1) + 1 ......... (n - 1)
(n + 1)³ = n³ + 3 * n² + 3 * n + 1 ......... (n)

Putting equation (n - 1) in equation n,
(n + 1)³ = (n - 1)³ + 3 * (n - 1)² + 3 * (n - 1) + 1 + 3 * n² + 3 * n + 1
         = (n - 1)³ + 3 * (n² + (n - 1)²) + 3 * ( n + (n - 1) ) + 1 + 1

By putting all equation, we get
(n + 1)³ = 1³ + 3 * ? k² + 3 * ? k + ? 1
n³ + 3 * n² + 3 * n + 1 = 1 + 3 * ? k² + 3 * (n * (n + 1))/2 + n
n³ + 3 * n² + 3 * n = 3 * ? k² + 3 * (n * (n + 1))/2 + n
n³ + 3 * n² + 2 * n - 3 * (n * (n + 1))/2 = 3 * ? k²
n * (n² + 3 * n + 2) - 3 * (n * (n + 1))/2 = 3 * ? k²
n * (n + 1) * (n + 2) - 3 * (n * (n + 1))/2 = 3 * ? k²
n * (n + 1) * (n + 2 - 3/2) = 3 * ? k²
n * (n + 1) * (2 * n + 1)/2  = 3 * ? k²
n * (n + 1) * (2 * n + 1)/6  = ? k²

Below is the implementation of this approach:

C++

// CPP Program to find sum 
// of square of first n
// natural numbers
#include <bits/stdc++.h>
using namespace std;
 
// Return the sum of square of
// first n natural numbers
int squaresum(int n)
{
    return (n * (n + 1) * (2 * n + 1)) / 6;
}
 
// Driven Program
int main()
{
    int n = 4;
    cout << squaresum(n) << endl;
    return 0;
}

Java

// 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 is contributed by Nikita Tiwari.*/

Python3

# Python3 Program to
# find sum of square 
# of first n natural 
# numbers
 
# Return the sum of 
# square of first n
# natural numbers
def squaresum(n) :
    return (n * (n + 1) * (2 * n + 1)) // 6
 
# Driven Program
n = 4
print(squaresum(n))
 
#This code is contributed by Nikita Tiwari.                                                               

C#

// C# Program to find sum
// of square of first n
// natural numbers
using System;
 
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()
 
    {
        int n = 4;
         
        Console.WriteLine(squaresum(n));
    }
}
 
/*This code is contributed by vt_m.*/

PHP

<?php
// PHP Program to find sum 
// of square of first n
// natural numbers
 
// Return the sum of square of
// first n natural numbers
function squaresum($n)
{
    return ($n * ($n + 1) * 
           (2 * $n + 1)) / 6;
}
 
// Driven Code
$n = 4;
echo(squaresum($n));
 
// This code is contributed by Ajit.
?>

Javascript

<script>
 
// Javascript program to find sum 
// of square of first n
// natural numbers
 
// Return the sum of square of
// first n natural numbers
function squaresum(n)
{
    return parseInt((n * (n + 1) * 
                     (2 * n + 1)) / 6);
}
 
// Driver code
let n = 4;
 
document.write(squaresum(n));
 
// This code is contributed by rishavmahato348
 
</script>

Output :

Time Complexity: O(1)

Auxiliary Space: O(1), since no extra space has been taken

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.

C++

// CPP Program to find sum of square of first
// n natural numbers. This program avoids
// overflow upto some extent for large value
// of n.
#include <bits/stdc++.h>
using namespace std;
 
// Return the sum of square of first n natural
// numbers
int squaresum(int n)
{
    return (n * (n + 1) / 2) * (2 * n + 1) / 3;
}
 
// Driven Program
int main()
{
    int n = 4;
    cout << squaresum(n) << endl;
    return 0;
}

Python3

# Python Program to find sum of square of first
# n natural numbers. This program avoids
# overflow upto some extent for large value
# of n.y
 
def squaresum(n):
    return (n * (n + 1) / 2) * (2 * n + 1) / 3
 
# main()
n = 4
print(squaresum(n));
 
# Code Contributed by Mohit Gupta_OMG <(0_o)>

Java

// 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)>

C#

// C# Program to find sum of square of first
// n natural numbers. This program avoids
// overflow upto some extent for large value
// of n.
 
using System;
 
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;
    }
 
    // Driver Code
    public static void Main()
    {
        int n = 4;
         
        Console.WriteLine(squaresum(n));
    }
}
 
// This Code is Contributed by vt_m.>

PHP

<?php
// PHP Program to find 
// sum of square of first
// n natural numbers. 
// This program avoids
// overflow upto some 
// extent for large value
// of n.
 
// Return the sum of square
// of first n natural numbers
function squaresum($n)
{
    return ($n * ($n + 1) / 2) * 
           (2 * $n + 1) / 3;
}
 
    // Driver Code
    $n = 4;
    echo squaresum($n) ;
     
// This code is contributed by vt_m.
?>

Javascript

<script>
 
// javascript Program to find sum of square of first
// n natural numbers. This program avoids
// overflow upto some extent for large value
// of n.
 
// Return the sum of square of first n natural
// numbers
function squaresum( n)
{
    return (n * (n + 1) / 2) * (2 * n + 1) / 3;
}
 
// Driven Program
 
    let n = 4;
     document.write(squaresum(n));
 
// This code contributed by aashish1995 
 
</script>

Output:

Time complexity: O(1) since performing constant operations

Space complexity: O(1) since using constant variables

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!