Sum Of Squares Of First N Natural Numbers
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.

Question

Sum Of Squares Of First N Natural Numbers

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.

Accepted Answer

The task is to find the sum of squares of the first 'N' natural numbers.

Iterate from 1 to N and calculate the square of each number
Add all the squares together to get the final sum
Return the sum as the result

Accepted Answer

Brute Force - Recursive

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.

Space Complexity: O(1)Explanation:

O(N), where ‘N’ is the given number.

Considering the recursive stack space.

Time Complexity: O(1)Explanation:

O(N), where ‘N’ is the given number.

Since we are traversing from 1 to ‘N’.

Accepted Answer

Brute Force - Iterative

Run a for loop from 1 to ‘N’.
Sum up the squares of each number from 1 to ‘N’.
Finally, return this sum.

Space Complexity: O(1)Explanation:

O(1)

Since we are using constant extra space.

Time Complexity: O(1)Explanation:

O(N), where ‘N’ is the given number.

Since we are traversing from 1 to ‘N’.

Accepted Answer

Mathematical Formula

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.

Space Complexity: O(1)Explanation:

O(1).

Since we are using constant extra space.

Time Complexity: O(1)Explanation:

O(1).

Since we are using a mathematical formula.

You are given an integer 'N'. You need to find the sum of squares of the first 'N' natural numbers.

For example:

Input Format:

Output Format:

Constraints:

Note:

Top Paytm Business Analyst interview questions & answers

Popular interview questions of Business Analyst

Top HR questions asked in Paytm Business Analyst