Sometimes we need to perform a single insertion in python, this can be easily done with the help of the insert function. But sometimes, we require to insert in a repeated manner after every n numbers, for that there can be numerous shorthands that can be quite handy. Lets discuss certain ways in which this can be done.
Method #1 : Using join() + enumerate() We can use the join function to join each of nth substring with the digit K and enumerate can do the task of performing the selective iteration of list.
Python3
# Python3 code to demonstrate # inserting K after every Nth number# using join() + enumerate()# initializing listtest_list = ['g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's']# printing original listprint ("The original list is : " + str(test_list))# initializing k k = 'x'# initializing NN = 3# using join() + enumerate()# inserting K after every Nth number res = list(''.join(i + k * (N % 3 == 2) for N, i in enumerate(test_list)))# printing result print ("The lists after insertion : " + str(res)) |
The original list is : [‘g’, ‘e’, ‘e’, ‘k’, ‘s’, ‘f’, ‘o’, ‘r’, ‘g’, ‘e’, ‘e’, ‘k’, ‘s’] The lists after insertion : [‘g’, ‘e’, ‘e’, ‘x’, ‘k’, ‘s’, ‘f’, ‘x’, ‘o’, ‘r’, ‘g’, ‘x’, ‘e’, ‘e’, ‘k’, ‘x’, ‘s’]
Time Complexity: O(n)
Auxiliary Space: O(n), where n is length of list.
Method #2 : Using itertools.chain() This method also has the ability to perform a similar task using an iterator and hence an improvement in the performance. This function performs a similar task but uses chain method to join the n substrings.
Python3
# Python3 code to demonstrate # inserting K after every Nth number# using itertool.chain()from itertools import chain# initializing listtest_list = ['g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's']# printing original listprint ("The original list is : " + str(test_list))# initializing k k = 'x'# initializing NN = 3# using itertool.chain()# inserting K after every Nth number res = list(chain(*[test_list[i : i+N] + [k] if len(test_list[i : i+N]) == N else test_list[i : i+N] for i in range(0, len(test_list), N)]))# printing result print ("The lists after insertion : " + str(res)) |
The original list is : [‘g’, ‘e’, ‘e’, ‘k’, ‘s’, ‘f’, ‘o’, ‘r’, ‘g’, ‘e’, ‘e’, ‘k’, ‘s’] The lists after insertion : [‘g’, ‘e’, ‘e’, ‘x’, ‘k’, ‘s’, ‘f’, ‘x’, ‘o’, ‘r’, ‘g’, ‘x’, ‘e’, ‘e’, ‘k’, ‘x’, ‘s’]
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(n), as we are creating a new list of the same size as the input list to store the result.
Method#3: Using Recursive method.
Algorithm:
- Define a recursive function insert_k_every_n_rec that takes four arguments: test_list, k, n, and idx. Here idx is the current index of the element we are considering.
- Base Case: if the end of the list is reached, return an empty list.
- Recursive Case: If (idx+1) % n == 0, add test_list[idx], k to the result list and call insert_k_every_n_rec again with incremented idx.
- Else, add test_list[idx] to the result list and call insert_k_every_n_rec again with incremented idx.
- Return the result list.
- Call insert_k_every_n_rec with test_list, k, and N as arguments and store the result in a variable res.
- Print the original list and the resulting list
Python3
def insert_k_every_n_rec(test_list, k, n, idx=0): if idx == len(test_list): # base case: end of list reached return [] elif (idx+1) % n == 0: # insert k after every n elements return [test_list[idx], k] + insert_k_every_n_rec(test_list, k, n, idx+1) else: return [test_list[idx]] + insert_k_every_n_rec(test_list, k, n, idx+1)# initializing listtest_list = ['g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's']# initializing kk = 'x'# initializing NN = 3# printing original listprint ("The original list is : " + str(test_list))# call the recursive function and print the resultres = insert_k_every_n_rec(test_list, k, N)# printing result print ("The lists after insertion : " + str(res)) |
The original list is : ['g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's'] The lists after insertion : ['g', 'e', 'e', 'x', 'k', 's', 'f', 'x', 'o', 'r', 'g', 'x', 'e', 'e', 'k', 'x', 's']
Time complexity: The time complexity of the recursive function insert_k_every_n_rec is O(n), where n is the length of the input list. Each element of the list is considered exactly once. The time complexity of the entire program is also O(n).
Auxiliary Space: The space complexity of the recursive function insert_k_every_n_rec is also O(n), as each recursive call adds an element to the result list. Therefore, the space complexity of the entire program is also O(n).
Method #4: Using a for loop with slicing and concatenation
This method works by looping over the indices of test_list in steps of n, and slicing the list at each step to get the sublist of length n. Then it concatenates this sublist with the k value and appends the result to the res list. Finally, it checks if the length of res is a multiple of n+1 (the length of the sublist plus the inserted k value) and removes the last element of res if necessary.
Step-by-step approach:
- Initialize an empty list named res to store the modified list.
- Loop through the indices of test_list in steps of n using the range function.
- At each step of the loop, slice the test_list to get the sublist of length n using the indices i to i+n.
- Concatenate the sublist with the k value and append the result to the res list using the += operator.
- Return res with the last element removed if the length of res is a multiple of n+1, else return res.
Below is the implementation of the above approach:
Python3
def insert_k_every_n(test_list, k, n): res = [] for i in range(0, len(test_list), n): res += test_list[i:i+n] + [k] return res[:-1] if len(res) % (n+1) == 0 else res# initializing listtest_list = ['g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's']# initializing kk = 'x'# initializing NN = 3# printing original listprint ("The original list is : " + str(test_list))# call the function and print the resultres = insert_k_every_n(test_list, k, N)# printing result print ("The lists after insertion : " + str(res)) |
The original list is : ['g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's'] The lists after insertion : ['g', 'e', 'e', 'x', 'k', 's', 'f', 'x', 'o', 'r', 'g', 'x', 'e', 'e', 'k', 'x', 's', 'x']
Time complexity: O(n), where n is the length of test_list. This is because the for loop iterates over test_list once.
Auxiliary Space: O(n), where n is the length of test_list. This is because the res list stores the modified list
Method #5 : Using for loop
Approach
- Initiated a for loop with i starting from 0 to len(test_list),initialise an empty output list
- Check if index is not 0 and index is divisible by N in such case, append k to output list and then append test_list[index] to output list
- If not append test_list[index] to output list
- Display output list at the end of for loop
Python3
#initializing listtest_list = ['g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's']# initializing kk = 'x'# initializing NN = 3# printing original listprint ("The original list is : " + str(test_list))# call the recursive function and print the resultres=[]for i in range(0,len(test_list)): if(i%N==0 and i!=0): res.append(k) res.append(test_list[i]) else: res.append(test_list[i])# printing resultprint ("The lists after insertion : " + str(res)) |
The original list is : ['g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's'] The lists after insertion : ['g', 'e', 'e', 'x', 'k', 's', 'f', 'x', 'o', 'r', 'g', 'x', 'e', 'e', 'k', 'x', 's']
Time Complexity : O(N) N -length of test_list
Auxiliary Space : O(N) N – length of output list (res)
