Find the Sum of First n Even Natural Numbers
FREE
Problem Statement
Given a number n. Find the sum of the first n even natural numbers.
Example
Input : 4
Output : 20
Explaination
The Sum of the first 4 natural numbers is 20 because 2+4+6+8 = 20
Constraints
1 <= N <= 10000
Approach 1: Naive Approach (Using a for Loop)
This is the Brute-Force method to find the sum of the first n even numbers. In this approach, we will be using a loop.
Algorithm
- Create a variable named sum to keep the track of the sum of the numbers till now in the loop
- Run a loop from i=1 to i=n
- do sum = sum+i*2
- Finally return the sum variable
C++ Implementation
Java Implementation
Python Implementation
Complexity Analysis
Time Complexity Analysis
- In this approach, we are running a loop from i=1 to i=n, which will take O(N) time.
- Inside the loop, we are doing sum = sum+i2, which will take O(1) time.
So the overall time complexity of this solution will be O(N)+O(1) = O(N)
Space Complexity Analysis
- In this approach, we are using only 1 variable i.e. sum, which will take O(1) space.
So the overall space complexity of this solution will be O(1)
Approach 2: Calculating the Nth Term
This is the best approach for calculating the sum of first n even numbers without using a loop and without using extra space. In this approach, we will be using a direct formula to calculate the sum of n first even numbers.
Algorithm
- This algorithm has a simple mathematical formula, we can calculate the sum of the first n numbers by using this formula sum = (n** * **(n+1))/2
- We also know that sum of the first n even numbers is two times the sum of the first n numbers, so the formula for sum of first n even numbers become sum = n * (n+1)
- So we have to just assign sum = n*(n+1), and return this variable
C++ Implementation
Java Implementation
Python Implementation
Complexity Analysis
Time Complexity Analysis
- In this approach, we are doing sum = n*(n+1), which will take O(1) time.
So the overall time complexity of this solution will be O(1)
Space Complexity Analysis
- In this approach, we are using only 1 variable i.e. sum, which will take O(1) space.
So the overall space complexity of this solution will be O(1)
Explore Scaler Topics Data Structures Tutorial and enhance your DSA skills with Reading Tracks and Challenges.
Conclusion
In this quick tutorial, we have discussed 2 different approaches for calculating the sum of first n-even numbers in C++, Java, and Python.
- In Approach 1, we used a for loop in which the time complexity is O(N) and space complexity is O(1).
- In Approach 2, we used the formula for calculating the sum of first n even numbers, and both time and space complexity for this approach became O(1).
Related Blogs
Frequently Asked Questions (FAQs)
What Is the Formula for Calculating the Sum of the First n Even Numbers?
The formula for the sum of the first n even numbers is sum = n * (n + 1).
This formula is derived as follows: The sum of an arithmetic progression is given by sum = (n/2) * (2a + (n-1) * d), where a is the first term and d is the common difference.
For the first n even numbers, the first term a=2 (since the first even number is 2) and the common difference d=2 (as even numbers are 2 units apart). Substituting these values into the formula, we get:
sum = (n/2) * (2 * 2 + (n-1) * 2) sum = (n/2) * (4 + 2n - 2) sum = (n/2) * (2 + 2n) sum = n * (n + 1)
Example:
For n = 4 (the first 4 even numbers are 2, 4, 6, 8):
Using the Formula: n * (n + 1) = 4 * (4 + 1) = 20 Manually: 2 + 4 + 6 + 8 = 20, thus verifying our formula is correct.
What Will be the Formula for Calculating the Sum of First n Odd Numbers?
A: The formula for the sum of the first n odd numbers will be sum = n*n
This formula can be derived as follows: As we know the sum of n numbers which are in the Arithmetic progression is given by sum = (n/2) * (2a+(n-1) * d)
So in the sum of the first n odd numbers, the first term is a=1 and the common difference is d=2. So by putting these values in the original formula, we get
sum = (n/2) * (2 * 1 + 2 * n - 2) sum = (n/2) * (2 * n) sum = n * n
Example:
Let n = 4, then sum = (4/2) * (2 + 2 * 4 -2) sum = (4/2) * (2 * 4) sum = 4 * 4 sum = 16 ( which is equal to n*n i.e. 4 * 4 )