# Optimizing method for counting length of elements between blocks

I'm currently trying to do a count of the number of elements between obstacles, for example:

000100001000 Would yield 3,4,3 and 01001110 would yield 1,2,1. More precisely i'm trying to find the sum of the above lengths passed to this function:

$f(x) = \frac {x(x+1)} {2}$

So the first example would yield a result of 22 (6+10+6) and the second would yield a result of 5 (1+3+1).

This is done repeatedly with the first element 'chopped off'. So for 000100001000, this would be calculated for 000100001000, 00100001000,0100001000 ,100001000 ,00001000 and so on (note that the answer for 10010 and 0010 would be the same since we're counting the distance between ones)

Currently i've just been using an $O(N^2)$ brute force approach, but i feel that i can easily improve this to O(N) since most of the information is already calculated after the very first element is processed. I'm wondering if there's a constant time method to process the subsequent elements after the first one is processed, but if not, what is the best approach?

Edit: I found a way to optimize the algorithm that requires this algorithm, but that implies that some of the zeroes could be transformed into ones when a digit is 'chopped off'. It's safe to assume that the element(s) that get transformed would be random. Eg: 0010 when chopped may transform into 011 or 110 or 111 instead

• If you solve the problems in reverse order by reading bits right-to-left, the constant-time-per-solution algorithm is hard to miss. – j_random_hacker Jul 11 '16 at 17:06
• @j_random_hacker How did i miss something so obvious.. I'll try to answer the question myself later today if somebody else doesn't answer it already by then. – Aayush Agrawal Jul 11 '16 at 17:09
• Well, I originally missed it too (maybe you saw my first, hastily-deleted comment?) But even if you process left-to-right, with a bit more bookkeeping (a queue of lengths) you can get a constant-time-per-solution algorithm pretty easily. – j_random_hacker Jul 11 '16 at 17:16
• @Evil If you go from right to left, you can compute the final sum as you go along and put them into an array. So for an array 1010, the values in your reference array would be 2 2 1 1. Chopping off the first element is as simple as just accessing the next point in the reference array that you just built. Constant time per query. – Aayush Agrawal Jul 11 '16 at 17:27
• @Evil: After computing the first solution, if you keep only O(1) state (e.g., the solution value) as opposed to O(n) state (e.g., all O(n) gap lengths, e.g. in a queue as I suggested) how do you correctly reduce the total when the first bit is chopped off? Remember, the per-gap score is quadratic in the length, so the amount to reduce by depends on the gap length. (I suppose you could scan forward until you hit the first 1-bit, and then output all answers for the preceding gap in reverse order -- this avoids a queue, but still seems more complicated than the right-to-left algorithm.) – j_random_hacker Jul 11 '16 at 17:39

One gap can be calculated as tetrahedral number $P(x) = \sum \limits _{i = 1} ^{i=x} f(i) = \frac{x * (x + 1) * (x + 2)}{6}$ where $f(i) = \frac{i * (i + 1)}{2}$
After calculating all gaps to calculate chopped off sum you need to subtract $P(x) - P(x-1)$ from the sum.