Sam
Sam

Reputation: 21

Find sub sequence of array that have negative multiplication

I'm trying to build an algorithm that given me count of subsequence that have a negative product of their elements.

For example:

Answer for [-1, 2, -3] is 4. ([-1] [-3] [-1, 2] and [2, -3])

Upvotes: 0

Views: 289

Answers (2)

MBo
MBo

Reputation: 80285

Linear algorithm (takes zeros into account).
At i-th step res is incremented by the number of negative-product subsequences ending in i-th position.

def cntneg(a):
    negcnt = 0
    poscnt = 1
    mul = 1
    res = 0
    for i in range(len(a)):
        if a[i]== 0:
            negcnt = 0
            poscnt = 1
            mul = 1
        else:
            if a[i] < 0:
                mul = - mul
            if mul > 0:
                res += negcnt
                poscnt += 1
            else:
                res += poscnt
                negcnt += 1
    return res

print(cntneg([-1, 2, -3, 4, -5, 0, -1, 2, 2, -3]))
>>15

Upvotes: 0

hilberts_drinking_problem
hilberts_drinking_problem

Reputation: 11602

A headache-proof way is to go with memoization. You can define a memoized function count_neg_seq_at(i) that returns the count of all negative subsequences starting at indexi. The function count_neq_seq_at(i) can be defined recursively in terms of count_neg_seq_at(i+1). The final answer is given by something like sum(count_neg_seq_at(i) for i = 1:n) where n is the length of the array.

Here is a Python implementation:

from functools import lru_cache
import numpy as np

np.random.seed(0)
arr = np.random.randint(-10, 10, 100)

# naive benchmark for checking correctness
from itertools import  combinations

def naive(xs):
  n = len(xs)
  count_neg = 0
  for i, j in combinations(range(n+1), 2):
    count_neg += sum(x < 0 for x in xs[i:j]) % 2
  return count_neg

# memoized approach
def count_negative_subseq(arr):
  neg = (arr < 0).astype(int)
  n = len(arr)
  # make a memoized function for counting negative subsequences
  # starting at a given index
  @lru_cache(None)
  def negative_starting_at(i):
    'number of subseqs with negative product starting at i'
    if i == n - 1:
      # base case: return one if the last element of the array is negative
      return neg[i]
    elif neg[i]:
      # if arr[i] is negative, return the count of positive product subsequences
      # from i+1 to n, plus one
      return n - i - negative_starting_at(i+1)
    else:
      # if arr[i] is positive, return count of negative product subsequences
      # from i+1 to n
      return negative_starting_at(i+1)

  # return sum of negative subsequences at each point
  return sum(negative_starting_at(i) for i in range(n))

print(naive(arr))
print(count_negative_subseq(arr))

# 2548
# 2548

Upvotes: 1

Related Questions