Количество подпоследовательностей с отрицательным произведением

Опубликовано: 1 Декабря, 2021

Для массива arr [] из N целых чисел задача состоит в том, чтобы найти количество всех подпоследовательностей массива, которые имеют отрицательные продукты.

Примеры:

Input: arr[] = {1, -5, -6}
Output: 4
Explanation
{-5}, {-6}, {1, -5} and {1, -6} are the only possible subsequences
Input: arr[] = {2, 3, 1}
Output: 0
Explanation
There is no such possible subsequence with negative product

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход:
Сгенерируйте все подпоследовательности массива и вычислите произведение всех подпоследовательностей. Если результат отрицательный, увеличьте счет на 1.

Эффективный подход:

Подсчитайте количество положительных и отрицательных элементов в массиве
Для подпоследовательности можно выбрать нечетное количество отрицательных элементов, чтобы сохранить отрицательный результат. Количество различных комбинаций подпоследовательностей с нечетным количеством отрицательных элементов будет pow (2, количество отрицательных элементов - 1)
Для подпоследовательности можно выбрать любое количество положительных элементов, чтобы сохранить отрицательный результат. Количество различных комбинаций подпоследовательностей со всеми положительными элементами будет pow (2, количество положительных элементов)

C ++

 // C++ implementation of the approach
 #include <bits/stdc++.h>
 using namespace std;
 // Function to return the count of all
 // the subsequences with negative product
 int cntSubSeq( int arr[], int n)
 {
    // To store the count of positive
    // elements in the array
    int pos_count = 0; 
    // To store the count of negative
    // elements in the array
    int neg_count = 0; 
    int result; 
    for ( int i = 0; i < n; i++) { 
        // If the current element
        // is positive
        if (arr[i] > 0)
            pos_count++;
        // If the current element
        // is negative
        if (arr[i] < 0)
            neg_count++;
    }
    // For all the positive
    // elements of the array
    result = pow (2, pos_count); 
    // For all the negative
    // elements of the array
    if (neg_count > 0)
        result *= pow (2, neg_count - 1);
    else
        result = 0;
    return result;
 }
 // Driver code
 int main()
 {
    int arr[] = { 3, -4, -1, 6 };
    int n = sizeof (arr) / sizeof (arr[0]); 
    cout << cntSubSeq(arr, n);
    return 0;
 }

Ява

 // Java implementation of the approach
 import java.util.*;
 class GFG
 {
 // Function to return the count of all
 // the subsequences with negative product
 static int cntSubSeq( int arr[], int n)
 {
    // To store the count of positive
    // elements in the array
    int pos_count = 0 ; 
    // To store the count of negative
    // elements in the array
    int neg_count = 0 ; 
    int result; 
    for ( int i = 0 ; i < n; i++)
    {
        // If the current element
        // is positive
        if (arr[i] > 0 )
            pos_count++;
        // If the current element
        // is negative
        if (arr[i] < 0 )
            neg_count++;
    }
    // For all the positive
    // elements of the array
    result = ( int ) Math.pow( 2 , pos_count); 
    // For all the negative
    // elements of the array
    if (neg_count > 0 )
        result *= Math.pow( 2 , neg_count - 1 );
    else
        result = 0 ; 
    return result;
 }
 // Driver code
 public static void main(String[] args)
 {
    int arr[] = { 3 ,- 4 , - 1 , 6 };
    int n = arr.length; 
    System.out.print(cntSubSeq(arr, n));
 }
 }
 // This code is contributed by ANKITKUMAR34

Python3

 # Python 3 implementation of the approach
 import math
 # Function to return the count of all
 # the subsequences with negative product
 def cntSubSeq(arr, n): 
    # To store the count of positive
    # elements in the array
    pos_count = 0 ; 
    # To store the count of negative
    # elements in the array
    neg_count = 0 
    for i in range (n): 
        # If the current element
        # is positive
        if (arr[i] > 0 ) :
            pos_count + = 1 
        # If the current element
        # is negative
        if (arr[i] < 0 ):
            neg_count + = 1 
    # For all the positive
    # elements of the array
    result = int (math. pow ( 2 , pos_count)) 
    # For all the negative
    # elements of the array
    if (neg_count > 0 ):
        result * = int (math. pow ( 2 , neg_count - 1 ))
    else :
        result = 0 
    return result
 # Driver code
 arr = [ 2 , - 3 , - 1 , 4 ]
 n = len (arr);
 print (cntSubSeq(arr, n)) 

C #

 // C# implementation of the approach
 using System;
 class GFG
 {
 // Function to return the count of all
 // the subsequences with negative product
 static int cntSubSeq( int []arr, int n)
 {
    // To store the count of positive
    // elements in the array
    int pos_count = 0; 
    // To store the count of negative
    // elements in the array
    int neg_count = 0; 
    int result; 
    for ( int i = 0; i < n; i++)
    {
        // If the current element
        // is positive
        if (arr[i] > 0)
            pos_count++;
        // If the current element
        // is negative
        if (arr[i] < 0)
            neg_count++;
    }
    // For all the positive
    // elements of the array
    result = ( int ) Math.Pow(2, pos_count); 
    // For all the negative
    // elements of the array
    if (neg_count > 0)
        result *= ( int )Math.Pow(2, neg_count - 1);
    else
        result = 0 ;
    return result;
 }
 // Driver code
 public static void Main(String[] args)
 {
    int []arr = { 3,-4, -1, 6 };
    int n = arr.Length; 
    Console.Write(cntSubSeq(arr, n));
 }
 }
 // This code is contributed by PrinciRaj1992

Javascript

 <script>
 // Javascript implementation of the approach
 // Function to return the count of all
 // the subsequences with negative product
 function cntSubSeq(arr, n)
 {
    
    // To store the count of positive
    // elements in the array
    var pos_count = 0; 
    // To store the count of negative
    // elements in the array
    var neg_count = 0; 
    var result; 
    for ( var i = 0; i < n; i++)
    {
        
        // If the current element
        // is positive
        if (arr[i] > 0)
            pos_count++;
        // If the current element
        // is negative
        if (arr[i] < 0)
            neg_count++;
    }
    // For all the positive
    // elements of the array
    result = Math.pow(2, pos_count);
    // For all the negative
    // elements of the array
    if (neg_count > 0)
        result *= Math.pow(2, neg_count - 1);
    else
        result = 0;
    return result;
 }
 // Driver code
 var arr = [ 3, -4, -1, 6 ];
 var n = arr.length;
 document.write(cntSubSeq(arr, n));
 // This code is contributed by noob2000
 </script>

Выход:

Сложность времени: O (n)
Другой подход:
Мы также можем подсчитать количество подпоследовательностей с отрицательным произведением, вычтя общее количество подпоследовательностей с положительными подпоследовательностями из общего количества подпоследовательностей .
Чтобы найти общее количество подпоследовательностей с положительным продуктом, используя подход, описанный в этой статье.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter Алгоритмы

Количество подпоследовательностей с отрицательным произведением

C ++

Ява

Python3

C #

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ