Count of index pairs in array whose range product is a positive integer
Given an array A of non-zero integers, the task is to find the number of pairs (l, r) where (l <= r) such that A[l]*A[l+1]*A[l+2]….A[r] is positive.
Examples:
Input: A = {5, -3, 3, -1, 1}
Output: 7
Explanation:
First pair, (1, 1) = 5 is positive
Second pair, (3, 3) = 3 is positive
Third pair, (1, 4) = 5 * -3 * 3 * -1 = 45 is positive
Forth pair, (2, 4) = -3 * 3 * -1 = 9 is positive
Fifth pair, (1, 5) = 5 * -3 * 3 * -1 * 1 = 45 is positive
Sixth pair, (2, 5) = -3 * 3 * -1 * 1 = 9 is positive
Seventh pair, (5, 5) = 1 is positive
So, there are seven pairs with positive product.
Input: A = {4, 2, -4, 3, 1, 2, -4, 3, 2, 3}
Output: 27
Approach:
The idea is to check possible number pairs for every array element.
- Iterate through an array, follow the below steps for every element in array.
- Keep a track of the number of elements having an even number of negative elements before them (as even_count) and number of elements having odd number of negative elements before them (as odd_count).
- Store the total number of negative elements till now (as total_count).
- If total_count is even then add even_count to the answer. Otherwise add odd_count.
Below is the implementation of the above approach:
C++
// C++ Program to find the // count of index pairs // in the array positive // range product #include <bits/stdc++.h> using namespace std; void positiveProduct( int arr[], int n) { int even_count = 0; int odd_count = 0; int total_count = 0; int ans = 0; for ( int i = 0; i < n; i++) { // Condition if number of // negative elements is even // then increase even_count if (total_count % 2 == 0) even_count++; // Otherwise increase odd_count else odd_count++; // Condition if current element // is negative if (arr[i] < 0) total_count++; // Condition if number of // negative elements is even // then add even_count // in answer if (total_count % 2 == 0) ans += even_count; // Otherwise add odd_count // in answer else ans += odd_count; } cout << ans << "\n" ; } // Driver Code int main() { int A[] = { 5, -3, 3, -1, 1 }; int size = sizeof (A) / sizeof (A[0]); positiveProduct(A, size); return 0; } |
Java
// Java program to find the count of // index pairs in the array positive // range product class GFG{ public static void positiveProduct( int arr[], int n) { int even_count = 0 ; int odd_count = 0 ; int total_count = 0 ; int ans = 0 ; for ( int i = 0 ; i < n; i++) { // Condition if number of // negative elements is even // then increase even_count if (total_count % 2 == 0 ) { even_count++; } // Otherwise increase odd_count else { odd_count++; } // Condition if current element // is negative if (arr[i] < 0 ) { total_count++; } // Condition if number of // negative elements is even // then add even_count // in answer if (total_count % 2 == 0 ) ans += even_count; // Otherwise add odd_count // in answer else ans += odd_count; } System.out.println(ans); } // Driver Code public static void main(String[] args) { int A[] = { 5 , - 3 , 3 , - 1 , 1 }; int size = A.length; positiveProduct(A, size); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program to find the count # of index pairs in the array # positive range product def positiveProduct(arr, n): even_count = 0 odd_count = 0 total_count = 0 ans = 0 for i in range (n): # Condition if number of # negative elements is even # then increase even_count if (total_count % 2 = = 0 ): even_count + = 1 # Otherwise increase odd_count else : odd_count + = 1 # Condition if current element # is negative if (arr[i] < 0 ): total_count + = 1 # Condition if number of # negative elements is even # then add even_count # in answer if (total_count % 2 = = 0 ): ans + = even_count # Otherwise add odd_count # in answer else : ans + = odd_count print (ans) # Driver Code if __name__ = = '__main__' : A = [ 5 , - 3 , 3 , - 1 , 1 ] size = len (A) positiveProduct(A, size) # This code is contributed by Shivam Singh |
C#
// C# program to find the count of // index pairs in the array positive // range product using System; class GFG{ public static void positiveProduct( int []arr, int n) { int even_count = 0; int odd_count = 0; int total_count = 0; int ans = 0; for ( int i = 0; i < n; i++) { // Condition if number of // negative elements is even // then increase even_count if (total_count % 2 == 0) { even_count++; } // Otherwise increase odd_count else { odd_count++; } // Condition if current element // is negative if (arr[i] < 0) { total_count++; } // Condition if number of // negative elements is even // then add even_count // in answer if (total_count % 2 == 0) ans += even_count; // Otherwise add odd_count // in answer else ans += odd_count; } Console.WriteLine(ans); } // Driver Code public static void Main(String[] args) { int []A = { 5, -3, 3, -1, 1 }; int size = A.Length; positiveProduct(A, size); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find the count of // index pairs in the array positive // range product function positiveProduct(arr,n) { let even_count = 0; let odd_count = 0; let total_count = 0; let ans = 0; for (let i = 0; i < n; i++) { // Condition if number of // negative elements is even // then increase even_count if (total_count % 2 == 0) { even_count++; } // Otherwise increase odd_count else { odd_count++; } // Condition if current element // is negative if (arr[i] < 0) { total_count++; } // Condition if number of // negative elements is even // then add even_count // in answer if (total_count % 2 == 0) ans += even_count; // Otherwise add odd_count // in answer else ans += odd_count; } document.write(ans); } // Driver Code let A = [5, -3, 3, -1, 1 ]; let size = A.length; positiveProduct(A, size); // This code is contributed by sravan kumar Gottumukkala </script> |
7
Time Complexity: O(N)
Space Complexity: O(1)
Contact Us