list comprehension
- Take input from the user as a positive integer N using the input() function.
- Convert the input string to an integer using the int() function and store it in a variable N.
- Use a list comprehension to create a list of squares of numbers from 1 to N. The list comprehension should look like this: [i*i for i in range(1, N+1)]. This creates a list of squares of numbers from 1 to N.
- Use the sum() function to find the sum of all elements in the list. Store the result in a variable sum_of_squares.
- Print the result using the print() function.
Python3
# Take input from user N = 5 # Use list comprehension to create list of squares squares_list = [i * i for i in range ( 1 , N + 1 )] # Find sum of squares using sum() function sum_of_squares = sum (squares_list) # Print the result print ( "Sum of squares of first" , N, "natural numbers is" , sum_of_squares) |
Output
Sum of squares of first 5 natural numbers is 55
The time complexity using a list comprehension is O(n)
The auxiliary space or space complexity is also O(n)
Python Program for Sum of squares of first n natural numbers
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.
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.*/ |
Output
30
Method 2: O(1)
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
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. |
Output
30
Time complexity: O(1)
Auxiliary space: O(1)
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.
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)> |
Output
30.0
Time complexity: O(1) because constant operations are being performed
Auxiliary space: O(1)
Contact Us