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.


  • $\begingroup$ 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$. $\endgroup$
    – lulu
    Nov 30, 2016 at 13:32
  • $\begingroup$ 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. $\endgroup$ Nov 30, 2016 at 13:40
  • $\begingroup$ 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? $\endgroup$
    – lulu
    Nov 30, 2016 at 13:43

1 Answer 1


Let $s$ denote the sequence.

Let $n$ denote the length of the sequence.

Then you could write the accumulated-reward formula as:


  • $\begingroup$ @Muhammadasifraza: You're welcome :) $\endgroup$ Nov 30, 2016 at 14:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .