Given a positive integer N. The task is to find 12 + 22 + 32 + ….. + N2.
Examples :
Input : N = 4 Output : 30 12 + 22 + 32 + 42 = 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 i2 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 numbersint 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 Programint main(){ int n = 4; cout << squaresum(n) << endl; return 0;} |
Java
// Java Program to find sum of // square of first n natural numbersimport 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 numbersdef 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 Programn = 4print(squaresum(n))# This code is contributed by Nikita Tiwari.*/ |
C#
// C# Program to find sum of// square of first n natural numbersusing 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 numbersfunction 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 numbersfunction 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 :
30
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)3 = k3 + 3 * k2 + 3 * k + 1
We can write the above identity for k from 1 to n:
23 = 13 + 3 * 12 + 3 * 1 + 1 ......... (1)
33 = 23 + 3 * 22 + 3 * 2 + 1 ......... (2)
43 = 33 + 3 * 32 + 3 * 3 + 1 ......... (3)
53 = 43 + 3 * 42 + 3 * 4 + 1 ......... (4)
...
n3 = (n - 1)3 + 3 * (n - 1)2 + 3 * (n - 1) + 1 ......... (n - 1)
(n + 1)3 = n3 + 3 * n2 + 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 * n2 + 3 * n + 1
= (n - 1)3 + 3 * (n2 + (n - 1)2) + 3 * ( n + (n - 1) ) + 1 + 1
By putting all equation, we get
(n + 1)3 = 13 + 3 * ? k2 + 3 * ? k + ? 1
n3 + 3 * n2 + 3 * n + 1 = 1 + 3 * ? k2 + 3 * (n * (n + 1))/2 + n
n3 + 3 * n2 + 3 * n = 3 * ? k2 + 3 * (n * (n + 1))/2 + n
n3 + 3 * n2 + 2 * n - 3 * (n * (n + 1))/2 = 3 * ? k2
n * (n2 + 3 * n + 2) - 3 * (n * (n + 1))/2 = 3 * ? k2
n * (n + 1) * (n + 2) - 3 * (n * (n + 1))/2 = 3 * ? k2
n * (n + 1) * (n + 2 - 3/2) = 3 * ? k2
n * (n + 1) * (2 * n + 1)/2 = 3 * ? k2
n * (n + 1) * (2 * n + 1)/6 = ? k2
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 numbersint squaresum(int n){ return (n * (n + 1) * (2 * n + 1)) / 6;}// Driven Programint main(){ int n = 4; cout << squaresum(n) << endl; return 0;} |
Java
// Java Program to find sum // of square of first n// natural numbersimport 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 numbersdef squaresum(n) : return (n * (n + 1) * (2 * n + 1)) // 6# Driven Programn = 4print(squaresum(n))#This code is contributed by Nikita Tiwari. |
C#
// C# Program to find sum// of square of first n// natural numbersusing 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 numbersfunction 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 numbersfunction squaresum(n){ return parseInt((n * (n + 1) * (2 * n + 1)) / 6);}// Driver codelet n = 4;document.write(squaresum(n));// This code is contributed by rishavmahato348</script> |
Output :
30
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// numbersint squaresum(int n){ return (n * (n + 1) / 2) * (2 * n + 1) / 3;}// Driven Programint 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.ydef squaresum(n): return (n * (n + 1) / 2) * (2 * n + 1) / 3# main()n = 4print(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 // numberspublic 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 numbersfunction 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// numbersfunction 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:
30
Time complexity: O(1) since performing constant operations
Space complexity: O(1) since using constant variables
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
