0
$\begingroup$

You have an array called $A$ of length $n$ (indexed from $0$), filled with numbers from interval $[1,n]$, not necessarily different. You need to know how many subarrays this array has in which every element is contained even number of times. Can you do it better than $O(n^2)$? An example: if the array is $3,5,5,7,3,7,3$, then the answer is $4$:

$3,5,5,7,3,7$

$5,5$

$5,5,7,3,7,3$

$7,3,7,3$

(firstly I wrote "subsets" instead of "subarrays", I am sorry for that because some people thought they solved my problem, but anyway I thank them for spent time)

I put this question to this website, because it's about algorithms, which is more connected to mathematics than informatics.

These are my algorithms:

firstly let's define some values:

$k$ - number of different numbers that appear in the array

$p$ - maximum number of repeating some number in the array (in my example $p=3$ because 3 is repeated $3$ times)

Algorithm No. $1$ ($O(n^2)$):

Main idea: for every index $0 \le i \le n-1$, count the number of arrays that begins in $i$.

So let say we have $i$. Make variables $j$,$S$ and array of bits $M$ of length $n$. Set $j=i-1$, $S=0$ and every element of $M$ to $0$. In every step do this, until you finished the step with $j=n-1$:

  • increase $j$ by $1$
  • let $t$ be the number on $j$-th position in array $A$. Change the value on $t$-th place in array $M$ (change means if it was $0$, change it to $1$, otherwise change it to $0$). If you changed element from $0$ to $1$, then increase $S$ by 1, otherwise decrease $S$ by 1.
  • if $S=0$ that means that every element from $i$-th to $j$-th place is repeated even number of times and we found a new subarray that satisfies the requirement.

Here , for every $i$ we have $n-i$ steps ($O(n)$), and we have $n$ different values for $i$. So the total complexity is $n \times O(n) = O(n^2)$

Algorithm No. $2$ ($O(nk)$):

I took idea for this from Radix sort

I really can't explain this formally, like the first algorithm.

Firstly make two arrays (let it again be $M$, and new array $T$) of length $n$. At beginning fill $T$ with numbers from $0$ to $n-1$. Take first number from the array (there are $k$ different numbers so we will make $k$ takes). Fill $M$ with parity of number of repeatings of that first number (call it $m$) in array $A$.

In my example $m=3$, and this would look like $M=\{1,1,1,1,0,0,1\}$

Now you can easily "sort" array $T$ using values from $M$ (in $O(n)$):

from this:

$T=\{0,1,2,3,4,5,6\}$

$M=\{1,1,1,1,0,0,1\}$

to this:

$T=\{4,5,0,1,2,3,6\}$

$M=\{0,0,1,1,1,1,1\}$

Now we have divided array $T$ into $2$ "blocks": first block is $\{4,5\}$, and the second one is $\{0,1,2,3,6\}$. Now fill $M$ on the same way, but for next number from array $A$.

Now $M$ looks like this: $\{0,1,0,0,0,0,0\}$

Now for every block (we have only $2$ for now) sort $T$ on the same way:

First block $\{4,5\}$ is marked as $\{0,0\}$ because $4$-th and $5$-th element from $M$ are both $0$, and we have nothing to sort, because all markings are $0$ so this block remains untouched as one block.

Second block $\{0,1,2,3,6\}$ is marked as $\{0,1,0,0,0\}$ in $M$. Now we need to divide this block into $2$ new blocks: $\{0,2,3,6\}$ and $\{1\}$. Now our $T$ looks like: $\{4,5,0,2,3,6,1\}$ (which is actually made from 3 blocks: $4,5|0,2,3,6|1$)

After third sorting our arrays would look like:

$M=\{0,0,0,1,1,0,0\}$

$T=\{5,4,0,2,6,3,1\}$ (now $T$ has 5 blocks: $5|4|0,2,6|3|1$)

What we did is actually sorting this table with respect to columns:

$1,1,1,1,0,0,1$ <-$M_1$

$0,1,0,0,0,0,0$ <-$M_2$

$0,0,0,1,1,0,0$ <-$M_3$

(0,1,2,3,4,5,6)

into this:

$0,0,1,1,1,1,1$

$0,0,0,0,0,0,1$

$0,1,0,0,0,1,0$

(5,4,0,2,6,3,1)

Now for every block of length $l$ we have $\frac {l(l-1)}{2}$ different subarrays. Let's take $3$-th block $\{0,2,6\}$ as an example: we have 3 different pairs $(0,2),(0,6),(2,6)$, and every pair $(x,y)$ corresponds to subarray from $(x+1)$-th element to $y$-th element from $A$, indexed from $0$. The special case is block that has only zeros (like $1$-st block in our example). For this block we should use this $\frac {l(l+1)}{2}$ instead of $\frac {l(l-1)}{2}$, because we don't have $-1$-st column in our table and some subarrays may begin with element indexed by $0$ where our $x$ would be $-1$. So our result would be:

$\frac {1(1+1)}{2}+\frac {1(1-1)}{2}+\frac {3(2-1)}{2}+\frac {1(1-1)}{2}+\frac {1(1-1)}{2}=1+0+3+0+0=4$, which is correct.

There are 2 more algorithms:

  • one with $O(p^2n \sqrt n)$, which is good for very small $p$, but in most cases this algorithm would run much faster, $O(p^2n \sqrt n)$ is only the worst case and few cases that look like the worst

  • and one with $O(n)$ which works if and only if $p=2$

But I don't have time to explain them right now, I need to go to bed, I will write them tomorrow, or in a few days, sorry.

$\endgroup$
  • $\begingroup$ Do you need subsets (order disregarded, can skip elements), subsequences (order regarded, can skip elements), or subarrays (order regarded, can not skip elements)? All of your examples are subarrays. Also, the naive (brute force) solution that I can think of is $\Omega(n^3)$. Can you explain your $\Theta(n^2)$ algorithm? $\endgroup$ – Noble Mushtak Apr 18 '16 at 16:07
  • $\begingroup$ @NobleMushtak ?? it is asked "how many subsets" not "list them all", so just count how many times each elements appears ($\mathcal{O}(n)$) and then compute the number of subsets only from those data $\endgroup$ – reuns Apr 18 '16 at 16:51
  • $\begingroup$ Your example is flawed: there are $7$ elements, hence $n=7$, but values exceed $7$. $\endgroup$ – Yves Daoust Apr 18 '16 at 16:54
  • 1
    $\begingroup$ I meant subarrays, look at my example. These arrays in my example are not just subsets, they are subarrays, sorry for that wrong word. $\endgroup$ – donaastor Apr 19 '16 at 16:53
  • $\begingroup$ I will put more datails on my question right now. $\endgroup$ – donaastor Apr 19 '16 at 16:55
1
$\begingroup$

If I understand what you are asking, you have a sequence of $n$ positive integers inclusively bound by $n$, and you want to find the number of subsets of indexes which produce sequences with only even multiplicities.

This can actually be done quite efficiently. I will be using binomial coefficients, which you can read up on if need be on the wiki page: https://en.wikipedia.org/wiki/Binomial_coefficient. The coefficient $k\choose m$ simply computes the number of subsets size $m$ contained in a set of size $k$.

First, for each number $k$ in range, identify how many even subsets of indexes there are that all have value $k$. This is given by the following sum: $1 + {k\choose{2}} + {k\choose{4}}{4\choose{2}}2! + {k\choose{6}}{6\choose{2}}3! + \cdots + {k\choose{2i}}{2i\choose{i}}i!$. The terms can be thought of as the number of ways to choose the indexes out of which to make $i$ pairs (given by first factor), multiplied by the number of ways to choose exactly how the pairs are laid out (given by remaining two factors). This product then is the total number of ways to choose $i$ pairs, so adding these terms for $2i\leq k$ gives the number of ways to choose pairs of indexes from the $k$ indexes which agree on a given value. The term of $1$ corresponds to $i=0$.

Note that the second binomial in the terms above, ${2i\choose{i}}$, can be thought of as choosing $i$ of the $2i$ indexes, and establishing them as first indexes for their respective pairs. The $i!$ can then be thought of as selecting the ordering of remaining indexes to use when assigning them as second elements to the pairs whose first elements are already selected.

Once one know the number of possible pairs for each value, one need only multiply these values together to get the number of solutions. Complexity will be about linearithmic in $n$, maybe a little worse, depending on how you count the complexity of base operations. It will be better with fewer repeated numbers. Complexity will be much better than $n^3$, the complexity of the brute force approach, or $n^2$, the complexity of some straightforward approaches, possibly including the one you referred to.

Two things to note. First, the binomial terms can be written in factorials and simplified. This is how you would actually compute them, but I have written them in binomial coefficients for clarity. Second, the empty set of indexes is counted here, so you may wish to subtract $1$ from your result to not count the empty set of indexes.

$\endgroup$
0
$\begingroup$

Although this doesn't seem to be what you're asking from the examples, if you only require them to be subsets (i.e. disregarding order and not necessarily continuous with respect to the original array), you can do $O(n)$.

int freq[n]
for num in arr:
   freq[num]++
result = 1   # empty set suffices
for num in freq:
   result *= freq[num] / 2 + 1
return result
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.