Sum of the series 2^0 + 2^1 + 2^2 +…..+ 2^n
Given an integer N, the task is to find the sum of series 20 + 21 + 22 + 23 + …. + 2n.
Examples:
Input: 5
Output: 31
20 + 21 + 22 + 23 + 24
= 1 + 2+ 4 + 8 + 16
= 31Input: 10
Output: 1023
20 + 21 + 2 2 + 23 + 2 4 + 25 + 26 + 27 + 2 8 + 29
= 1 + 2+ 4 + 8 + 16 + 32 +64 + 128 + 256 + 512
= 1023
A naive approach is to calculate the sum is to add every power of 2 from 0 to n.
Below is the implementation of above approach:
C++
// C++ program to find sum #include <bits/stdc++.h> using namespace std; // function to calculate sum of series int calculateSum( int n) { // initialize sum as 0 int sum = 0; // loop to calculate sum of series for ( int i = 0; i < n; i++) { // calculate 2^i // and add it to sum sum = sum + (1 << i); } return sum; } // Driver code int main() { int n = 10; cout << "Sum of series of power of 2 is : " << calculateSum(n); } |
Java
// Java program to find sum class GFG { // function to calculate sum of series static int calculate sum( int n) { // initialize sum as 0 int sum = 0 ; // loop to calculate sum of series for ( int i = 0 ; i < n; i++) { // calculate 2^i // and add it to sum sum = sum + ( 1 << i); } return sum; } // Main function public static void main(String[] args) { int n = 10 ; System.out.println( "Sum of the series : " + calculateSum(n)); } }; |
Python3
# Python3 program to calculate # sum of series of power of 2 # function to calculate sum of series def calculateSum(n): sum = 0 # loop to calculate sum of series for i in range ( 0 , n): # calculate 2 ^ i sum = sum + ( 1 << i) return sum # Driver code n = 10 print ( "Sum of series " , calculateSum(n)) |
C#
// C# program to find sum using System; class GFG { // function to calculate // sum of series static int calculateSum( int n) { // initialize sum as 0 int sum = 0; // loop to calculate // sum of series for ( int i = 0; i < n; i++) { // calculate 2^i // and add it to sum sum = sum + (1 << i); } return sum; } // Driver code public static void Main() { int n = 10; Console.WriteLine( "Sum of the series : " + calculateSum(n)); } } // This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php // PHP program to find sum of the // series 2^0 + 2^1 + 2^2 +…..+ 2^n // function to calculate // sum of series function calculateSum( $n ) { // initialize sum as 0 $sum = 0; // loop to calculate // sum of series for ( $i = 0; $i < $n ; $i ++) { // calculate 2^i // and add it to sum $sum = $sum + (1 << $i ); } return $sum ; } // Driver code $n = 10; echo "Sum of the series of " . "power 2 is : " , calculateSum( $n ); // This code is contributed // by Smitha ?> |
Javascript
<script> // Javascript program to find sum of the // series 2^0 + 2^1 + 2^2 +…..+ 2^n // function to calculate // sum of series function calculateSum(n) { // initialize sum as 0 let sum = 0; // loop to calculate // sum of series for (let i = 0; i < n; i++) { // calculate 2^i // and add it to sum sum = sum + (1 << i); } return sum; } // Driver code let n = 10; document.write( "Sum of the series of power 2 is : " + calculateSum(n)) //This code is contributed by sravan kumar </script> |
Output:
Sum of series of power of 2 is : 1023
Time Complexity: O(n)
Auxiliary Space: O(1)
An efficient approach is to find the 2^(n+1) and subtract 1 from it since we know that 2^n can be written as:
2n = ( 20+21+22+23+24 +...... 2n-1) +1
Below is the implementation of above approach:
C++
// C++ program to find sum #include <bits/stdc++.h> using namespace std; int calculateSum( int n) { // calculate and return 2^(n+1) -1 return (1 << (n + 1)) - 1; } int main() { int n = 10; cout << "Sum of series of power of 2 is :" << calculateSum(n); } |
Java
// Java program to calculate // sum of series of power of 2 class GFG { // function to calculate sum of series static int calculate sum( int n) { // calculate 2^(n+1) int sum = ( 1 << (n + 1 )); return sum - 1 ; } // Driver code public static void main(String[] args) { int n = 10 ; System.out.println( "Sum of the series of power 2 is : " + calculateSum(n)); } }; |
Python3
# Python3 program to calculate # sum of series of 2's power # function to calculate sum of series def calculateSum(n): # calculate 2^(n + 1) sum = ( 1 << (n + 1 )) return sum - 1 # Driver code n = 10 print ( "Sum of series " , calculateSum(n)) |
C#
// C# program to calculate // sum of series of power of 2 using System; class GFG { // function to calculate // sum of series static int calculateSum( int n) { // calculate 2^(n+1) int sum = (1 << (n + 1)); return sum - 1; } // Driver code public static void Main() { int n = 10; Console.Write( "Sum of the series " + "of power 2 is : " + calculateSum(n)); } // This code is contributed // by Smitha } |
PHP
<?php // PHP program to calculate // sum of series of power of 2 // function to calculate // sum of series function calculateSum( $n ) { // calculate 2^(n+1) $sum = (1 << ( $n + 1)); return $sum - 1; } // Driver code $n = 10; echo "Sum of the series of " . "power 2 is : " , calculateSum( $n ); // This code is contributed // by Smitha |
Javascript
<script> // Javascript program to calculate // sum of series of power of 2 // function to calculate // sum of series function calculateSum(n) { // calculate 2^(n+1) let sum = (1 << (n + 1)); return sum - 1; } // Driver code let n = 10; document.write( "Sum of the series of power 2 is : " + calculateSum(n)); // This code is contributed by sravan kumar </script> |
Output:
Sum of series of power of 2 is :2047
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us