4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ If you solve the problems in reverse order by reading bits right-to-left, the constant-time-per-solution algorithm is hard to miss. $\endgroup$ – j_random_hacker Jul 11 '16 at 17:06
  • $\begingroup$ @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. $\endgroup$ – Aayush Agrawal Jul 11 '16 at 17:09
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Jul 11 '16 at 17:16
  • $\begingroup$ @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. $\endgroup$ – Aayush Agrawal Jul 11 '16 at 17:27
  • $\begingroup$ @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.) $\endgroup$ – j_random_hacker Jul 11 '16 at 17:39
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ To calculate the length of the gap, you need to iterate through the array till you've found the next 1. But if that's the case, you can skip all the rest entirely and just just the right-to-left approach. $\endgroup$ – Aayush Agrawal Jul 11 '16 at 18:24
  • $\begingroup$ However i managed to modify the problem a bit and the RTL approach would no longer work for that. I'd appreciate any help with the modified problem. $\endgroup$ – Aayush Agrawal Jul 11 '16 at 18:25
  • $\begingroup$ I do not fully understand the edit and the change 0 to 1. Yes you have to know gap size but instead of calculating all the sums you calculate it once so for gap of size 20 you get sum of all sizes 1 to 20 in one move. $\endgroup$ – Evil Jul 11 '16 at 18:28

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.