Longest sub-array with positive product

Easy
0/40
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
ArcesiumBig BasketFlipkart limited

Problem statement

You are given an array ‘ARR’ of ‘N’ integers, you need to find the maximum length of the sub-array such that the product of elements of the sub-array is positive.

For Example: 
Let us say we have array 'ARR' =[-1,3,5,-2,4,-9]. The longest sub-array with the positive product is [3,5,-2,4,-9].
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains ‘N’ which is the number of elements in the array.

The second line of each test case contains ‘N’ space-separated integers that make up ‘ARR’.
Output Format 
For each test case, print a single line containing a single integer denoting the length of the longest sub-array with a positive product.

The output of each test case will be printed in a separate line.
Note 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints 
1 <= T <= 50
1 <= N <= 10 ^ 5
-10 ^ 8 <= ARR[i] <= 10 ^ 8

Time Limit: 1 sec.
Sample Input 1
2
5
-3 7 -5 9 4 
6 
8 4 0 -3 -54 6
Sample Output 1
5
3
Explanation
Test Case 1: The given array is [-3, 7, -5, 9, 4]. 
We can clearly see that product of all the elements of the array is positive. Therefore the longest length of sub-array with the positive product is ‘5’.

Test Case 2: The given array is [8, 4, 0, -3, -54, 6].
Sub-arrays with the positive product are [8, 4] and [-3, -54, 6]. And the longer sub-array is of length ‘3’.
Sample Input 2
1 
8
-1 2 3 4 5 0 8 0
Sample Output 2
4
Hint

Check the product of all sub-arrays.

Approaches (2)
Naive Approach

A naive approach is to iterate through all elements and examine the product of all the possible sub-arrays. But we have to only check whether the product is positive or not, so instead of multiplying numbers, we will multiply only the signs of numbers.

 

Algorithm:

  • Take a variable ‘PR’ to keep the product and ‘ANS’ (initialized to 0) to store the result.
  • Run three loops
    • ‘i’ : 0 to ‘N - 1’
    • ‘j’ : ‘i’  to ‘N - 1’
    • ‘k’ : ‘i’ to ‘j’
  • ‘i’ indicates the starting index of the current sub-array, and ‘j’ indicates the sub-array’s ending index.
  • Run loop of ‘k’ from ‘i’ to ‘j’
    • If (ARR [k] > 0 ) , ‘PR' = ‘PR’ * 1;
    • If (ARR [k] < 0 ) , 'PR' = 'PR' * -1;
    • If (ARR [k] > 0 ) , ‘PR’ = ‘PR’ * 0;
  • If ‘PR’ > 0, update ‘ANS’ as ‘ANS’ =max(ANS, j - i + 1).
  • Return ‘ANS’.
Time Complexity

O(N ^ 3), where ‘N’ is the size of the array.

 

As we have run three loops, so a total of N ^ 3 operations will be performed. Therefore complexity is of order N ^ 3.

Space Complexity

O(1).

 

Since constant space is used.

Code Solution
(100% EXP penalty)
Longest sub-array with positive product
Full screen
Console