Python Program to Get K initial powers of N
Given size K and value N, the task is to write a Python Program to compute a list of powers of N till K.
Input : N = 4, K = 6 Output : [1, 4, 16, 64, 256, 1024] Explanation : 4^i is output till i = K. Input : N = 3, K = 6 Output : [1, 3, 9, 27, 81, 243] Explanation : 3^i is output till i = K.
Method #1 : Using list comprehension + ** operator
In this, the values are incremented till K using list comprehension and ** is used to get required power of numbers.
Python3
# Python3 code to demonstrate working of # Get K initial powers of N # Using list comprehension + ** operator # initializing N N = 4 # printing original list print ( "The original N is : " + str (N)) # initializing K K = 6 # list comprehension provides shorthand for problem res = [N * * idx for idx in range ( 0 , K)] # printing result print ( "Square values of N till K : " + str (res)) |
The original N is : 4 Square values of N till K : [1, 4, 16, 64, 256, 1024]
Time Complexity: O(n)
Auxiliary Space: O(1)
Method #2 : Using pow() + list comprehension
In this, we perform the task of computing power using pow(), the rest of all the functions are performed using list comprehension.
Python3
# Python3 code to demonstrate working of # Get K initial powers of N # Using pow() + list comprehension from math import pow # initializing N N = 4 # printing original list print ( "The original N is : " + str (N)) # initializing K K = 6 # list comprehension provides shorthand for problem # squaring using pow() res = [ int ( pow (N, idx)) for idx in range ( 0 , K)] # printing result print ( "Square values of N till K : " + str (res)) |
The original N is : 4 Square values of N till K : [1, 4, 16, 64, 256, 1024]
Time complexity: O(n), where n is the length of the test_list. The pow() + list comprehension takes O(n) time
Auxiliary Space: O(1), no extra space of is required
Method #3 : Using Numpy
Note: Install numpy module using command “pip install numpy”
Python3
# Python3 code to demonstrate working of # Get K initial powers of N # Using NumPy import numpy as np # initializing N N = 4 # printing original list print ( "The original N is : " + str (N)) # initializing K K = 6 # using np.power() to get squares res = np.power(N, np.arange(K)) # printing result print ( "Square values of N till K : " + str (res)) |
Output:
The original N is : 4 Square values of N till K : [1, 4, 16, 64, 256, 1024]
Time Complexity: O(K)
Auxiliary Space: O(K)
Method #4 : Using operator.pow()
- Initiated a for loop from i=1 to K
- Raised N to power of i using operator.pow() and appended to output list
- Displayed output list
Python3
# Python3 code to demonstrate working of # Get K initial powers of N import operator # initializing N N = 4 # printing original list print ( "The original N is : " + str (N)) # initializing K K = 6 res = [] for i in range ( 1 ,K + 1 ): res.append(operator. pow (N,i)) # printing result print ( "Square values of N till K : " + str (res)) |
The original N is : 4 Square values of N till K : [4, 16, 64, 256, 1024, 4096]
Time Complexity: O(K)
Auxiliary Space: O(K)
Method #5: Using a simple loop
We can solve this problem using a simple loop that iterates from 1 to K and computes the power of N for each iteration.
Python3
# Python3 code to demonstrate working of # Get K initial powers of N import operator # initializing N N = 4 # printing original list print ( "The original N is : " + str (N)) # initializing K K = 6 res = [] for i in range ( 1 , K + 1 ): res.append(N * * i) # printing result print ( "Square values of N till K : " + str (res)) |
The original N is : 4 Square values of N till K : [4, 16, 64, 256, 1024, 4096]
Time complexity: O(K)
Auxiliary space: O(1) because it only requires a single variable to store the result at each iteration.
Method #6: Using recursion
step-by-step approach
- Define a function named “powers_of_n” that takes two arguments, N and K.
- Inside the function, check if the value of K is equal to 1. If it is, return a list containing the value of N.
- If the value of K is not equal to 1, call the “powers_of_n” function recursively with the arguments N and K-1.
- Store the result of the recursive call in a variable named “powers”.
- Append the value of N raised to the power of K to the “powers” list.
- Return the “powers” list.
- Define two variables, N and K, with values of 4 and 6 respectively.
- Call the “powers_of_n” function with the arguments N and K, and store the result in a variable named “res”.
- Print the “res” list using the “print” function and a formatted string.
Python3
def powers_of_n(N, K): if K = = 1 : return [N] else : powers = powers_of_n(N, K - 1 ) powers.append(N * * K) return powers N = 4 K = 6 res = powers_of_n(N, K) print ( "Square values of N till K : " + str (res)) |
Square values of N till K : [4, 16, 64, 256, 1024, 4096]
Time complexity: O(K)
Auxiliary space: O(K) (for the recursive call stack)
Method #7: Using heapq:
Algorithm:
- Define a function called powers_of_n that takes two arguments N and K.
- Check if K is equal to 1.
a. If yes, return a list with a single element which is the value of N. - If K is not equal to 1, recursively call the powers_of_n function with N and K-1 as arguments.
- Append the value of N raised to the power of K to the list obtained in step 3.
- Return the list obtained in step 4.
- Define the values of N and K and call the powers_of_n function with these values.
- Print the list obtained in step 5.
Python3
import heapq def powers_of_n(N, K): res = [] heap = [] heapq.heappush(heap, N) while len (res) < K: x = heapq.heappop(heap) res.append(x) heapq.heappush(heap, x * N) return res N = 4 K = 6 res = powers_of_n(N, K) # printing original list print ( "The original N is : " + str (N)) print ( "Square values of N till K : " + str (res)) #This code is contributed by Vinay Pinjala |
The original N is : 4 Square values of N till K : [4, 16, 64, 256, 1024, 4096]
Time complexity: O(K)
The function recursively calls itself K times, each time reducing the value of K by 1. Therefore, the time complexity of the function is O(K).
Space complexity: O(K)
The function uses a list to store the values of N raised to the power of K. The size of the list is K. Therefore, the space complexity of the function is O(K).
Contact Us