Given a Tuple, nesting at 2nd position, return summation of 1st elements.
Input : test_tup = (5, (6, (1, (9, None))))
Output : 21
Explanation : 9 + 6 + 5 + 1 = 21.Input : test_tup = (5, (6, (1, None)))
Output : 12
Explanation : 1 + 6 + 5 = 12.
Method #1: Using infinite loop
In this, we perform get into skew structure while summation using infinite loop and break when we reach None value.
Python3
# Python3 code to demonstrate working of # Skew Nested Tuple Summation# Using infinite loop# initializing tupletest_tup = (5, (6, (1, (9, (10, None)))))# printing original tupleprint("The original tuple is : " + str(test_tup))res = 0while test_tup: res += test_tup[0] # assigning inner tuple as original test_tup = test_tup[1]# printing result print("Summation of 1st positions : " + str(res)) |
The original tuple is : (5, (6, (1, (9, (10, None))))) Summation of 1st positions : 31
Time complexity: O(n), where n is the number of elements in the input tuple.
Auxiliary space: O(1), as only a constant amount of additional memory is used to store the variables test_tup and res, regardless of the size of the input tuple.
Method #2: Using recursion
In this, we perform summation and recur for the 2nd element of tuple, return on None.
Python3
# Python3 code to demonstrate working of # Skew Nested Tuple Summation# Using recursion# helper function to perform taskdef tup_sum(test_tup): # return on None if not test_tup: return 0 else: return test_tup[0] + tup_sum(test_tup[1])# initializing tupletest_tup = (5, (6, (1, (9, (10, None)))))# printing original tupleprint("The original tuple is : " + str(test_tup))# calling fnc.res = tup_sum(test_tup)# printing result print("Summation of 1st positions : " + str(res)) |
The original tuple is : (5, (6, (1, (9, (10, None))))) Summation of 1st positions : 31
The time complexity of the given code is O(n), where n is the number of elements in the input nested tuple.
The auxiliary space used by the given code is O(n), where n is the number of elements in the input nested tuple.
Method 3: Using isinstance() + recursion
Recursively traverses the nested tuple and adds up the first element of each tuple it encounters.
- The tup_sum() function takes in a tuple test_tup as input.
- The base case for the recursion is when test_tup is an empty tuple or a tuple with no integer elements. In this case, the function returns 0 to stop the recursion.
- If the base case is not met, the function assumes that the first element of test_tup is an integer and adds it to the result. Then, the function recursively calls itself with the remaining elements of test_tup (i.e., test_tup[1:]), which may themselves be tuples.
- The recursion continues until the base case is met, at which point the function returns the total sum of the first elements of all the tuples encountered during the traversal.
Python3
def tup_sum(test_tup): # Base case: return 0 for empty tuple or tuple with no integer elements if not test_tup or not isinstance(test_tup[0], int): return 0 else: # Recursively compute sum of first element of current tuple and remaining tuples return test_tup[0] + tup_sum(test_tup[1:])# Example tupletest_tup = (5, (6, (1, (9, (10, None)))))# Print original tupleprint("The original tuple is:", test_tup)# Compute sum of first elementsres = tup_sum(test_tup)# Print result print("Sum of first elements:", res) |
The original tuple is: (5, (6, (1, (9, (10, None))))) Sum of first elements: 5
Time complexity: O(n), where n is the total number of elements in the nested tuple.
Auxiliary space: O(m), where m is the maximum depth of the nested tuple.
Method #4: Using a stack data structure
In this implementation, we use a stack to traverse the nested tuple. We start by adding the entire tuple to the stack. In each iteration, we pop an element from the stack and check if it’s an integer or a tuple. If it’s an integer, we add it to the result. If it’s a tuple, we push its first and second elements onto the stack (in that order). We continue this process until the stack is empty, and then return the result.
Python3
# Python3 code to demonstrate working of # Skew Nested Tuple Summation# Using stack# initializing tupletest_tup = (5, (6, (1, (9, (10, None)))))# function to compute sum of first elements using stackdef sum_first_elements(test_tup): stack = [] res = 0 stack.append(test_tup) while stack: curr = stack.pop() if isinstance(curr, int): res += curr elif curr: stack.append(curr[1]) stack.append(curr[0]) return res# printing original tupleprint("The original tuple is : " + str(test_tup))# printing resultprint("Summation of 1st positions : " + str(sum_first_elements(test_tup))) |
The original tuple is : (5, (6, (1, (9, (10, None))))) Summation of 1st positions : 31
Time complexity: O(n), where n is the total number of elements in the nested tuple.
Auxiliary space: O(h), where h is the maximum depth of the nested tuple.
Method 5; using a generator function and the built-in sum function
- The program defines a generator function called get_first_element that takes a tuple as an argument.
- Inside the generator function, the program checks if the argument passed is a tuple. If it is, then it yields the first element of the tuple using the index tup[0].
- The program then recursively calls the get_first_element function with the second element of the tuple using tup[1].
- If the argument passed to the function is not a tuple, then the function does not yield anything and the recursion stops.
- The program initializes a nested tuple called test_tup that contains integers and nested tuples.
- The program prints the original tuple using the print function.
- The program calculates the sum of the first elements of the nested tuples in test_tup by calling the get_first_element generator function using the sum function. The result is stored in the res variable.
- The program prints the result using the print function.
Python3
# Python3 code to demonstrate working of # Skew Nested Tuple Summation# Using a generator function and sum# define generator function to yield first element of each nested tupledef get_first_element(tup): if isinstance(tup, tuple): yield tup[0] yield from get_first_element(tup[1])# initializing tupletest_tup = (5, (6, (1, (9, (10, None)))))# printing original tupleprint("The original tuple is : " + str(test_tup))# calculate sum of first elements using generator and sumres = sum(get_first_element(test_tup))# printing result print("Summation of 1st positions : " + str(res)) |
The original tuple is : (5, (6, (1, (9, (10, None))))) Summation of 1st positions : 31
Time complexity for this method is O(n) where n is the number of elements in the nested tuple.
Auxiliary space is O(1) because the generator function yields each first element one at a time, without storing them all in memory at once.
