Last Updated: 9 Dec, 2020
Sum Of Squares Of First N Natural Numbers
Easy
Asked in companies
You are given an integer 'N'. You need to find the sum of squares of the first 'N' natural numbers.
For example:
If 'N' = 4. You need to return 1^2 + 2^2 + 3^2 + 4^2 = 30.
Input Format:
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.
The first and the only line of each test case contains an integer 'N'.
Output Format:
For each test case, return the sum of squares of the first 'N' natural numbers in a single line.
Constraints:
1 ≤ T ≤ 10^4
1 ≤ N ≤ 5*10^5
where 'T' is the number of test cases and 'N' is the given number.
Time Limit: 1 sec.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Approaches
- Write a recursive solution for adding the sum of the squares of the first ‘N’ natural numbers.
- The base case would be the sum of the first natural number, which is 1.
- Sum up the squares of each number from 1 to ‘N’.
- Finally, return this sum.
- Run a for loop from 1 to ‘N’.
- Sum up the squares of each number from 1 to ‘N’.
- Finally, return this sum.
- The sum of squares of first N natural numbers is given by: 1^2 + 2^2 + … N^2 = N*(N+1)*(2*N+1)/6
- This can be proved by mathematical induction.
- We can see that the formula is true for N = 1. Because 1*(1+1)*(2*1+1)/6 = 1.
- Let’s assume that the formula is true for N = K. That is 1^2 + 2^2 + … K^2 = K*(K+1)*(2*K+1)/6.
- Now for N = K + 1. The sum would be: 1^2 + 2^2 + K^2 + (K+1)^2 = K*(K+1)*(2*K+1)/6 + (K+1)^2 = (K+1)*[(K*(2*K+1)) + 6*(K+1)]/6 = (K+1)*(2K^2 + 7K + 6)/6 = (K+1)*(K+2)*(2*(K+1)+1)/6
- Hence the formula is proved.