# how to write formula for following problem

I am trying to write a formula to compute an accumulated reward for the following case.

Let we have a series of 1 and 0 and we want to identify if there is contiguous set of 1's exist? For every contiguous 1 (atleast two 1's and upper limit unbounded) we give 0 reward and for every non-contiguous existence we add a unit penalty reward.

For example, if we have series 001100010010. Then our formula should give us 2 as there are two non-contiguous elements.

thanks,

• What sort of formula are you hoping for? Recursively: if your string ends in $0$, then the value is the same as it is for the (shorter) string with the $0$ removed. If it ends in $01^a$ for $a>1$ then you can remove that entire block without changing the value. If it ends in $01$ then you can delete that block, and increase the value by $1$.
– lulu
Nov 30, 2016 at 13:32
• A simple summation formula that should count the number of non-contiguous, non-zero elements in a given series. For example, for the series given in the question we can remove first 7 elements and then count 1 for next "10" then we can remove next 0 and then count 1 for next "10". So the total count for this series is 2. Nov 30, 2016 at 13:40
• Well, as I say, and as your example illustrates, there is a simple recursion. My earlier comment defines the recursive step. If you strings are very long, you could look to parallelize the process (you can cut it in half with a few simple rules and handle the two pieces separately). I don't know what you mean by "summation"....what would you want to sum over?
– lulu
Nov 30, 2016 at 13:43

Let $s$ denote the sequence.
Let $n$ denote the length of the sequence.
$$(s_{1})(1-s_{2})+(s_{n})(1-s_{n-1})+\sum\limits_{n=2}^{n-1}(s_{n})(1-s_{n-1})(1-s_{n+1})$$