Given a list containing Positive and Negative integers, We have to find number of times the sign(Positive or Negative) changes in the list.
Input: [-1, 2, 3, -4, 5, -6, 7, 8, -9, 10, -11, 12] Output:9 Explanation : Sign change from -1 to 2, ans = 1 Sign change from 3 to -4, ans = 2 Sign change from -4 to 5, ans = 3 Sign change from 5 to -6, ans = 4 Sign change from -6 to 7, ans = 5 Sign change from 8 to -9, ans = 6 Sign change from -9 to 10, ans = 7 Sign change from 10 to -11 ans = 8 Sign change from -11 to 12, ans = 9 Input: [-1, 2, 3, -4, 5, -11, 12] Output:5 Explanation : Sign change from -1 to 2, ans = 1 Sign change from 3 to -4, ans = 2 Sign change from -4 to 5, ans = 3 Sign change from 5 to -11, ans = 4 Sign change from -11 to 12, ans = 5
Let’s discuss certain ways in which this task is performed.
Method #1: Using Iteration Using Iteration to find number of time sign changes in the list.
Python3
# Python Code to find number of # time sign changes in the list.# Input list InitializationInput = [-1, 2, 3, -4, 5, -6, 7, 8, -9, 10, -11, 12] # Variable Initializationprev = Input[0]ans = 0# Using Iterationfor elem in Input: if elem == 0: sign = -1 else: sign = elem / abs(elem) if sign == -prev: ans = ans + 1 prev = sign# Printing answerprint(ans) |
9
Time complexity: O(n),We are iterating over the given list Input of length n just once. Therefore, the time complexity of the given code is O(n).
Space complexity: O(1),We have not used any extra space for the given code. Therefore, the space complexity is O(1).
Method #2: Using Itertools and groupby This is yet another way to perform this particular task using itertools.
Python3
# Python Code to find number of # time sign changes in the list. # Input list Initialization Input = [-1, 2, 3, -4, 5, -6, 7, 8, -9, 10, -11, 12] # Importing import itertools # Using groupby Output = len(list(itertools.groupby(Input, lambda Input: Input > 0))) Output = Output -1# Printing output print(Output) |
9
Time Complexity: O(n), where n is the length of the list.
Space Complexity: O(n), where n is the length of the list. This is because we are creating a list of the same length as the input list in order to group the elements.
Method #3: Using Zip The most concise and readable way to find number of time sign changes in the list is using zip.
Python3
# Python Code to find number of # time sign changes in the list. # Using zip to check def check(Input): Input = [-1 if not x else x for x in Input] # zip with leading 1, so that opening negative value is # treated as sign change return sum((x ^ y)<0 for x, y in zip([1]+Input, Input)) # Input list Initialization Input = [-1, 2, 3, -4, 5, -6, 7, 8, -9, 10, -11, 12] Output = check(Input) Output = Output -1# Printing output print(Output) |
9
Time Complexity : O(N),The time complexity of the above code is O(N), because it iterates over the list once.
Space Complexity : O(1),The space complexity is O(1) because no additional space is used.
Method #4: Using recursion
This function uses recursion to iterate through the list and check for sign changes. The base case is an empty list, in which case it returns 0. Otherwise, it checks the sign of the first element and recurses with the rest of the list. It also checks for a sign change with the second element in the list and adds it to the recursive call’s result.
Python3
def sign_changes(lst): # Base case: empty or single element list if not lst or len(lst) == 1: return 0 # Check sign of first element sign = 1 if lst[0] >= 0 else -1 # Recurse with rest of list and check for sign change return sign_changes(lst[1:]) + (sign != (1 if lst[1] >= 0 else -1))# Test sign_changes functionlst1 = [-1, 2, 3, -4, 5, -6, 7, 8, -9, 10, -11, 12]print(sign_changes(lst1)) # 9lst2 = [-1, 2, 3, -4, 5, -11, 12]print(sign_changes(lst2)) # 5#This code is contributed by Edula Vinay Kumar Reddy |
9 5
Time complexity for this approach is O(n) where n is the length of the list.
Auxiliary Space is O(n) for this approach, as the recursive calls are stacked and a new stack frame is created for each recursive call.
Method #5: Using Numpy Library.
Algorithm:
- Convert the input list to a numpy array.
- Calculate the sign of each element of the array using np.sign() function.
- Compare the signs of adjacent elements using np.sign(Input[1:]) != np.sign(Input[:-1]).
- Count the number of True values in the above array using np.sum().
- Print the count as the answer.
Python3
import numpy as np# Input list Initialization Input = np.array([-1, 2, 3, -4, 5, -6, 7, 8, -9, 10, -11, 12])ans = np.sum(np.sign(Input[1:]) != np.sign(Input[:-1]))# Printing output print(ans)#This code is contributed by TvSk |
Output
9
Time Complexity: O(n), where n is the length of the input list. The np.sign() function and element-wise comparison using != are performed in O(n) time complexity. The np.sum() function takes O(1) time complexity in this case.
Space Complexity: O(n), as we are creating a numpy array of size n to store the input list.
