Given a positive integer N, the task is to express 2^N in the sum of powers of 2 and in exactly N+1 terms. Print those N+1 terms.
Example:
Input: N = 4
Output: 1 1 2 4 8
Explanation: 2^4 = 2^0 + 2^0 + 2^1 + 2^2 + 2^3 = 1 + 1 + 2 + 4 + 8Input: N = 5
Output: 1 1 2 4 8 16
Approach: As we know:
2^0 + 2^1 +…. 2^(N-1) = 2^N -1
Therefore, adding 1 at the beginning of the series of powers of 2 will result in 2^N in exactly N+1 terms.
1 + 2^0 + 2^1 +…. 2^(N-1) = 2^N
Below is the implementation of the above approach
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find exactly N + 1 terms// of powers of 2 series, whose sum is 2^Nvoid powerOf2(long long N){ cout << 1 << ' '; for (int i = 0; i < N; ++i) { cout << (long long)pow(2, i) << ' '; }}// Driver Codeint main(){ long long N = 5; powerOf2(N);} |
Java
// Java program for the above approachimport java.util.*;public class GFG{// Function to find exactly N + 1 terms// of powers of 2 series, whose sum is 2^Nstatic void powerOf2(long N){ System.out.print(1); for (int i = 0; i < N; ++i) { System.out.print(" " + (long)Math.pow(2, i)); }}// Driver Codepublic static void main(String args[]){ long N = 5; powerOf2(N);}}// This code is contributed by Samim Hossain Mondal |
C#
// C# program for the above approachusing System;class GFG{// Function to find exactly N + 1 terms// of powers of 2 series, whose sum is 2^Nstatic void powerOf2(long N){ Console.Write(1); for (int i = 0; i < N; ++i) { Console.Write(" " + (long)Math.Pow(2, i)); }}// Driver Codepublic static void Main(){ long N = 5; powerOf2(N);}}// This code is contributed by Samim Hossain Mondal |
Python3
# Python3 program for the above approachimport math# Function to find exactly N + 1 terms# of powers of 2 series, whose sum is 2^Ndef powerOf2(N) : print(1,end= ' '); for i in range(N) : print(int(math.pow(2, i)),end = ' ');# Driver Codeif __name__ == "__main__" : N = 5; powerOf2(N); # This code is contributed by AnkThon |
Javascript
<script>// JavaScript program for the above approach// Function to find exactly N + 1 terms// of powers of 2 series, whose sum is 2^Nfunction powerOf2(N){ document.write(1 + ' '); for (var i = 0; i < N; ++i) { document.write(Math.pow(2, i) + ' '); }}// Driver CodeN = 5;powerOf2(N);// This code is contributed by AnkThon</script> |
Output
1 1 2 4 8 16
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Share your thoughts in the comments
