Python Program to find number of sub arrays with negative product

This post deals with how to find the number of sub-arrays with negative products in Python. Here, I am going to provide you with a simple solution to this problem using prefix product array.

Example:

Input:

arr[ ]={6, 7, -2}

Output:

3

Explanation:

Following are the sub-arrays with the negative product: {2}, {6,-2}, {7,-2}

Program

Now, we have a look at the implementation of the above algorithm.

def negativeProduct(arr, size): 
    posCount = 1
    negCount = 0
    for x in range(size):  
        if (arr[x] > 0): 
            arr[x] = 1
        else: 
            arr[x] = -1 
        if (x > 0): 
            arr[x] *= arr[x - 1]
       #to count the number of postive and negative
       #elements in Prefix product array
        if (arr[x] == 1): 
            posCount += 1
        else: 
            negCount += 1 
    return (posCount * negCount) 
arr = list(map(int,input("Enter the elements: ").split()))
size = len(arr) 
print("Number of sub-array with negative product:",negativeProduct(arr,size))

Sample output 1:

Enter the elements: 6 7 -2 
Number of sub-array with negative product: 3

Sample output 2:

Enter the elements: 6 2 8
Number of sub-array with negative product: 0

I hope that you have learned something new and useful from this post.

Leave a Reply

Your email address will not be published. Required fields are marked *