is there an algorithm for this array problem?

ferocioussprouts 0
Viewed 109

I'm struggling to find an algorithm for this problem that runs in O(n) worst case time.

Let's say you have an array, of n elements, with the value of the elements being either 1 or 0. I need to calculate the number of sub-arrays where there exists more 1's inside the sub-array than there are 0's outside the sub-array.

what i tried to do:

i tried to first make a prefix-sum array of the input array, this is so that when given a sub-array, we grab the start and end indexes of the sub array, look at the corresponding values in the prefix array -> we can find out the number of 1s in the sub-array in O(n) time.

for example:

input array = [1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1]

prefix sum array = [0, 1, 1, 1, 2, 3, 3, 4, 4, 4, 5, 6, 6, 7]

example sub array = [1,0,0,1]

start index = 0, end index = 3

prefix[3+1] - prefix[0] = 2 - 0 = 2 (two 1s inside the sub

array)

I am not sure where to go from here. Help would be much appreciated.

arrays algorithm
2 Answers

It is a very strange constraint, but after making the following observation it becomes easy:

Enlarging the sub-array always improves its value. We define the value v = i - o, whith i being the ones inside the sub-array and o the number of zeros outside the sub-array. Now another way to formulate the problem is: count all sub-arrays with a value greater than zero. Here is why the value always improves when enlarging the array:

  • adding a 0 to the sub-array: v = i - (o - 1) = i - o + 1 this is one greater compared to i - o.
  • adding a 1 to the sub-array: v = (i + 1) - o = i - o + 1 this is one greater compared to i - o.

So we can see that enlarging the sub-array not only increases its value, enlarging the sub-array by n elements increases the score exactly by n. Also decreasing the size of the sub-array by n decreases its value by n. This leads to the conclusion that we can calculate a minimum size for the sub-array and then use that number and the array size to get the number of sub-arrays fullfilling the condition.

So here is an O(n) algorithm:

  1. Count the number of 0s in the array => z
  2. if z = n return 0
  3. The size making the value 0 is: m = z (by counting the zeros we look at it like having a sub-array of size 0, so the number of ones inside is 0 and the number of zeros outside is z, this gives a value v = 0 - z = -z, so if we increase the size by z we get a value of 0)
  4. So finally we can start at index 0 with a sub-array, here we can count all sub-arrays of sizes m < size < n, so the number of sub-arrays for index 0 is n - m, at index 1 it is n - m - 1 and at index i it is n - m - i (as long as the therm is > 0). Because we know the term will reach zero because the minimum size for the sub-array is 1 we can get the following formula: count = (n - m) * (n - m + 1) / 2

And condensed: count the number of 0s z and return (n - z) * (n - z + 1) / 2

Which is the same as counting the number of 1s i and return i * (i + 1) / 2 (because n - z = i)

maraca0

The number of sub-arrays with more ones inside than zeroes outside is the i-th triangular number, where i is the number of ones in the entire input array. Here is a proof.

Let n be the number of elements in the input array, and i the number of ones in the input array.

For any sub-array A, let s(A) be its size (number of elements inside), and let v(A) be its value, that is the number of ones inside minus the number of zeroes outside. The sub-array counts if v(A) > 0.

The only sub-array of size n has value i (if s(A) = n, then v(A) = i), so if i > 0, that sub-array counts.

For any sub-array A and two constants t and w,
if s(A) = t => v(A) = w then s(A) = t-1 => v(B) = w-1.
In other words, if all sub-arrays of size t have value w, then all sub-arrays of size t-1 have value w-1. This is because any sub-array of size t-1 can be obtained by excluding an element from a sub-array of size t, and whatever that element is, its exclusion decreases the value of the sub-array by exactly 1: it's either 1 more zero outside, or 1 less one inside.

By induction, for any sub-array A, if s(A) = n-t then v(A) = i-t. Additionally, the converse is true: if v(A) = i-t then s(A) = n-t, because if s(A) != s(B) then v(A) != v(B).

For any sub-array A, A counts only if v(A) = i-t where t < i, so only if s(A) = n-t where t < i. There are n-(t-1) sub-arrays of size t (1 of size n, 2 of size n-1, ..., n of size 1), so there are n-(n-t-1) = t+1 sub-arrays of size n-t. And the sum of t+1 from t = 0 to t = i-1 equals i*(i+1)/2, also known as the i-th triangular number.

In conclusion, count the number of ones in the input array and compute the corresponding triangular number. In pseudo-code:

input_array = [1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1]
ones_count = 0

for i in input_array
    if i == 1 then ones_count++

answer = ones_count * (ones_count+1) / 2
Nelfeal0
Related