Posted on by Kalkicode
Code Mathematics

Sum of squares of first n natural numbers in constant time

The problem at hand is to calculate the sum of squares of the first 'n' natural numbers in constant time complexity. In mathematical terms, we need to find the value of 1 2 + 2 2 + 3 2 + + n 2 1^2 + 2^2 + 3^2 + \ldots + n^2 n2 using an approach that doesn't depend on the value of 'n'. Traditional approaches have linear time complexity, but we aim to achieve this in constant time.

Problem Statement

Given a positive integer 'n', we want to compute the sum of the squares of the first 'n' natural numbers.

Example

Let's consider two test cases to illustrate the problem:

Test Case 1

For n = 5 n = 5 , we need to calculate 1 2 + 2 2 + 3 2 + 4 2 + 5 2 = 55 1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 55 .

Test Case 2

For n = 8 n = 8 , we need to calculate 1 2 + 2 2 + 3 2 + 4 2 + 5 2 + 6 2 + 7 2 + 8 2 = 204 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2 + 8^2 = 204 .

Idea to Solve

The key to solving this problem in constant time lies in utilizing a mathematical formula derived from the sum of squares of consecutive integers. The formula is:

1 2 + 2 2 + 3 2 + + n 2 = n ( n + 1 ) ( 2 n + 1 ) 6 1^2 + 2^2 + 3^2 + \ldots + n^2 = \frac{n \cdot (n + 1) \cdot (2n + 1)}{6} n2=6n(n+1)(2n+1)

Pseudocode

squaresOfNaturalNo(n):
    if n > 0:
        sum = (n * (n + 1) * (2 * n + 1)) / 6
    Display "Sum of square in", n, "natural number is", sum

Algorithm Explanation

  1. Check if n n is greater than 0.
  2. If true, calculate the sum using the formula: sum = n ( n + 1 ) ( 2 n + 1 ) 6 \text{sum} = \frac{n \cdot (n + 1) \cdot (2n + 1)}{6} .
  3. Display the calculated result.

Output Explanation

For the provided test cases:

  1. For n = 5 n = 5 , the sum is calculated using the formula: sum = 5 ( 5 + 1 ) ( 2 5 + 1 ) 6 = 55 \text{sum} = \frac{5 \cdot (5 + 1) \cdot (2 \cdot 5 + 1)}{6} = 55 .
  2. For n = 8 n = 8 , the sum is calculated using the formula: sum = 8 ( 8 + 1 ) ( 2 8 + 1 ) 6 = 204 \text{sum} = \frac{8 \cdot (8 + 1) \cdot (2 \cdot 8 + 1)}{6} = 204 .

Code Solution

/*
    C program for
    Sum of squares of first n natural numbers in constant time
*/
#include <stdio.h>

void squaresOfNaturalNo(int n)
{
	long long int sum = 0;
	if (n > 0)
	{
		sum = ((n *(n + 1) *(2 *n + 1)) / 6);
	}
	// Display calculated result
	printf(" Sum of square in %d natural number is %lld \n", n, sum);
}
int main(int argc, char const *argv[])
{
	/*
	   Test A
	   n = 5
	   (1)² + (2)² + (3)² + (4)² + (5)²  = 55
	*/
	squaresOfNaturalNo(5);
	/*
	   Test A
	   n = 8
	   (1)² + (2)² + (3)² + (4)² + (5)² + (6)² + 
	   (7)² + (8)²  = 204
	*/
	squaresOfNaturalNo(8);
	return 0;
}

Output

 Sum of square in 5 natural number is 55
 Sum of square in 8 natural number is 204
/*
    Java program for
    Sum of squares of first n natural numbers in constant time
*/
public class NaturalNumbers
{
	public void squaresOfNaturalNo(int n)
	{
		long sum = 0;
		if (n > 0)
		{
			sum = ((n * (n + 1) * (2 * n + 1)) / 6);
		}
		// Display calculated result
		System.out.print("\n Sum of square in " + 
                         n + " natural number is " + sum);
	}
	public static void main(String[] args)
	{
		NaturalNumbers task = new NaturalNumbers();
		/*
		   Test A
		   n = 5
		   (1)² + (2)² + (3)² + (4)² + (5)²  = 55
		*/
		task.squaresOfNaturalNo(5);
		/*
		   Test B
		   n = 8
		   (1)² + (2)² + (3)² + (4)² + (5)² + (6)² + 
		   (7)² + (8)²  = 204
		*/
		task.squaresOfNaturalNo(8);
	}
}

Output

 Sum of square in 5 natural number is 55
 Sum of square in 8 natural number is 204
// Include header file
#include <iostream>
using namespace std;
/*
    C++ program for
    Sum of squares of first n natural numbers in constant time
*/
class NaturalNumbers
{
	public: void squaresOfNaturalNo(int n)
	{
		long sum = 0;
		if (n > 0)
		{
			sum = ((n *(n + 1) *(2 *n + 1)) / 6);
		}
		// Display calculated result
		cout << "\n Sum of square in " << n 
      		 << " natural number is " << sum;
	}
};
int main()
{
	NaturalNumbers *task = new NaturalNumbers();
	/*
	   Test A
	   n = 5
	   (1)² + (2)² + (3)² + (4)² + (5)²  = 55
	*/
	task->squaresOfNaturalNo(5);
	/*
	   Test B
	   n = 8
	   (1)² + (2)² + (3)² + (4)² + (5)² + (6)² + 
	   (7)² + (8)²  = 204
	*/
	task->squaresOfNaturalNo(8);
	return 0;
}

Output

 Sum of square in 5 natural number is 55
 Sum of square in 8 natural number is 204
// Include namespace system
using System;
/*
    Csharp program for
    Sum of squares of first n natural numbers in constant time
*/
public class NaturalNumbers
{
	public void squaresOfNaturalNo(int n)
	{
		long sum = 0;
		if (n > 0)
		{
			sum = ((n * (n + 1) * (2 * n + 1)) / 6);
		}
		// Display calculated result
		Console.Write("\n Sum of square in " +
                      n + " natural number is " + sum);
	}
	public static void Main(String[] args)
	{
		NaturalNumbers task = new NaturalNumbers();
		/*
		   Test A
		   n = 5
		   (1)² + (2)² + (3)² + (4)² + (5)²  = 55
		*/
		task.squaresOfNaturalNo(5);
		/*
		   Test B
		   n = 8
		   (1)² + (2)² + (3)² + (4)² + (5)² + (6)² + 
		   (7)² + (8)²  = 204
		*/
		task.squaresOfNaturalNo(8);
	}
}

Output

 Sum of square in 5 natural number is 55
 Sum of square in 8 natural number is 204
package main
import "fmt"
/*
    Go program for
    Sum of squares of first n natural numbers in constant time
*/
func squaresOfNaturalNo(n int) {
	var sum int64 = 0
	if n > 0 {
		sum = int64((n * (n + 1) * (2 * n + 1)) / 6)
	}
	// Display calculated result
	fmt.Print("\n Sum of square in ", 
		n, " natural number is ", sum)
}
func main() {

	/*
	   Test A
	   n = 5
	   (1)² + (2)² + (3)² + (4)² + (5)²  = 55
	*/
	squaresOfNaturalNo(5)
	/*
	   Test B
	   n = 8
	   (1)² + (2)² + (3)² + (4)² + (5)² + (6)² + 
	   (7)² + (8)²  = 204
	*/
	squaresOfNaturalNo(8)
}

Output

 Sum of square in 5 natural number is 55
 Sum of square in 8 natural number is 204
<?php
/*
    Php program for
    Sum of squares of first n natural numbers in constant time
*/
class NaturalNumbers
{
	public	function squaresOfNaturalNo($n)
	{
		$sum = 0;
		if ($n > 0)
		{
			$sum = ((($n * ($n + 1) * (2 * $n + 1)) / 6));
		}
		// Display calculated result
		echo("\n Sum of square in ".$n.
			" natural number is ".$sum);
	}
}

function main()
{
	$task = new NaturalNumbers();
	/*
	   Test A
	   n = 5
	   (1)² + (2)² + (3)² + (4)² + (5)²  = 55
	*/
	$task->squaresOfNaturalNo(5);
	/*
	   Test B
	   n = 8
	   (1)² + (2)² + (3)² + (4)² + (5)² + (6)² + 
	   (7)² + (8)²  = 204
	*/
	$task->squaresOfNaturalNo(8);
}
main();

Output

 Sum of square in 5 natural number is 55
 Sum of square in 8 natural number is 204
/*
    Node JS program for
    Sum of squares of first n natural numbers in constant time
*/
class NaturalNumbers
{
	squaresOfNaturalNo(n)
	{
		var sum = 0;
		if (n > 0)
		{
			sum = (((n * (n + 1) * (2 * n + 1)) / 6));
		}
		// Display calculated result
		process.stdout.write("\n Sum of square in " +
                             n + " natural number is " + sum);
	}
}

function main()
{
	var task = new NaturalNumbers();
	/*
	   Test A
	   n = 5
	   (1)² + (2)² + (3)² + (4)² + (5)²  = 55
	*/
	task.squaresOfNaturalNo(5);
	/*
	   Test B
	   n = 8
	   (1)² + (2)² + (3)² + (4)² + (5)² + (6)² + 
	   (7)² + (8)²  = 204
	*/
	task.squaresOfNaturalNo(8);
}
main();

Output

 Sum of square in 5 natural number is 55
 Sum of square in 8 natural number is 204
#    Python 3 program for
#    Sum of squares of first n natural numbers in constant time
class NaturalNumbers :
	def squaresOfNaturalNo(self, n) :
		sum = 0
		if (n > 0) :
			sum = (((n * (n + 1) * (2 * n + 1)) / 6))
		
		#  Display calculated result
		print("\n Sum of square in ", 
              n ," natural number is ", 
              sum, end = "")
	

def main() :
	task = NaturalNumbers()
	#   Test A
	#   n = 5
	#   (1)² + (2)² + (3)² + (4)² + (5)²  = 55
	task.squaresOfNaturalNo(5)
	#   Test B
	#   n = 8
	#   (1)² + (2)² + (3)² + (4)² + (5)² + (6)² + 
	#   (7)² + (8)²  = 204
	task.squaresOfNaturalNo(8)

if __name__ == "__main__": main()

Output

 Sum of square in  5  natural number is  55.0
 Sum of square in  8  natural number is  204.0
#    Ruby program for
#    Sum of squares of first n natural numbers in constant time
class NaturalNumbers 
	def squaresOfNaturalNo(n) 
		sum = 0
		if (n > 0) 
			sum = ((n * (n + 1) * (2 * n + 1)) / 6)
		end

		#  Display calculated result
		print("\n Sum of square in ", n ," natural number is ", sum)
	end

end

def main() 
	task = NaturalNumbers.new()
	#   Test A
	#   n = 5
	#   (1)² + (2)² + (3)² + (4)² + (5)²  = 55
	task.squaresOfNaturalNo(5)
	#   Test B
	#   n = 8
	#   (1)² + (2)² + (3)² + (4)² + (5)² + (6)² + 
	#   (7)² + (8)²  = 204
	task.squaresOfNaturalNo(8)
end

main()

Output

 Sum of square in 5 natural number is 55
 Sum of square in 8 natural number is 204
/*
    Scala program for
    Sum of squares of first n natural numbers in constant time
*/
class NaturalNumbers()
{
	def squaresOfNaturalNo(n: Int): Unit = {
		var sum: Long = 0;
		if (n > 0)
		{
			sum = ((n * (n + 1) * (2 * n + 1)) / 6);
		}
		// Display calculated result
		print("\n Sum of square in " + n + " natural number is " + sum);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: NaturalNumbers = new NaturalNumbers();
		/*
		   Test A
		   n = 5
		   (1)² + (2)² + (3)² + (4)² + (5)²  = 55
		*/
		task.squaresOfNaturalNo(5);
		/*
		   Test B
		   n = 8
		   (1)² + (2)² + (3)² + (4)² + (5)² + (6)² + 
		   (7)² + (8)²  = 204
		*/
		task.squaresOfNaturalNo(8);
	}
}

Output

 Sum of square in 5 natural number is 55
 Sum of square in 8 natural number is 204
/*
    Swift 4 program for
    Sum of squares of first n natural numbers in constant time
*/
class NaturalNumbers
{
	func squaresOfNaturalNo(_ n: Int)
	{
		var sum: Int = 0;
		if (n > 0)
		{
			sum = ((n * (n + 1) * (2 * n + 1)) / 6);
		}
		// Display calculated result
		print("\n Sum of square in", n ,
              "natural number is", 
              sum, terminator: "");
	}
}
func main()
{
	let task: NaturalNumbers = NaturalNumbers();
	/*
	   Test A
	   n = 5
	   (1)² + (2)² + (3)² + (4)² + (5)²  = 55
	*/
	task.squaresOfNaturalNo(5);
	/*
	   Test B
	   n = 8
	   (1)² + (2)² + (3)² + (4)² + (5)² + (6)² + 
	   (7)² + (8)²  = 204
	*/
	task.squaresOfNaturalNo(8);
}
main();

Output

 Sum of square in 5 natural number is 55
 Sum of square in 8 natural number is 204
/*
    Kotlin program for
    Sum of squares of first n natural numbers in constant time
*/
class NaturalNumbers
{
	fun squaresOfNaturalNo(n: Int): Unit
	{
		var sum = 0;
		if (n > 0)
		{
			sum = ((n * (n + 1) * (2 * n + 1)) / 6);
		}
		// Display calculated result
		print("\n Sum of square in " + 
              n + " natural number is " + sum);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: NaturalNumbers = NaturalNumbers();
	/*
	   Test A
	   n = 5
	   (1)² + (2)² + (3)² + (4)² + (5)²  = 55
	*/
	task.squaresOfNaturalNo(5);
	/*
	   Test B
	   n = 8
	   (1)² + (2)² + (3)² + (4)² + (5)² + (6)² + 
	   (7)² + (8)²  = 204
	*/
	task.squaresOfNaturalNo(8);
}

Output

 Sum of square in 5 natural number is 55
 Sum of square in 8 natural number is 204

Time Complexity

The given algorithm has a constant time complexity since it performs a fixed number of arithmetic operations regardless of the value of n n . Therefore, the time complexity of this algorithm is O ( 1 ) O(1) .

In conclusion, this article has explained how to calculate the sum of squares of the first 'n' natural numbers in constant time using a mathematical formula. This approach is efficient and provides a significant advantage over traditional linear-time methods for large values of 'n'.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment