Detecting Sequences of Zeroes in an Array

Question

I have some arrays and I want to count the number of sequences of zeroes in the array.

For example:

 A [0][0][1][1][1][0][0][0][2][2][2][2][0][0][0]

would return 3 sequences

How can I do this efficiently?

Edit: the language I am interested in using to solve is

Javascript

Truly, the most efficient way will depend on what language is being used. Something like J or APL probably has a three or four character solution. C# would probably prefer a LINQ solution. Plain C, you're going to have to count. What are you using? — Ross Presser
– Ross Presser, Commented Mar 21, 2017 at 2:49
Would one zero surrounded by non-zeros considered a sequence? — Sash Sinha
– Sash Sinha, Commented Mar 21, 2017 at 2:49
@RossPresser I though LINQ was a slower than a for loop due to increased overhead — Bennett Yeo
– Bennett Yeo, Commented Mar 21, 2017 at 2:50
@shash678 for this specific problem, only sequences of 2 zeroes or more are a sequence. Thus a single zero would not count, and in fact will not ever be constructed by the algo. — sova
– sova, Commented Mar 21, 2017 at 5:39

ruakh · Accepted Answer · 2017-03-21 02:52:27Z

2

You can just count the zeroes that are followed by either nonzero or end-of-array. For example, in Java:

int result = 0;
for (int i = 0; i < A.length; ++i) {
    if (A[i] == 0 && (i + 1 == A.length || A[i+1] != 0)) {
        ++result;
    }
}
return result;

answered Mar 21, 2017 at 2:52

ruakh

185k29 gold badges292 silver badges324 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

sova Over a year ago

Thanks, but the minimum length is 2 zeroes. How would we modify this to accommodate a new fact?

ruakh Over a year ago

@sova: According to your above comment, "a single zero [...] will not ever be constructed by the algo". So this answer should still work for you.

sova Over a year ago

I was planning on using the answer to this question to be part of the check that ensures that fact, so it's a bit of a fun irony, but yes I'll accept your answer, @ruakh

sova Over a year ago

I believe a successful modification would need just another AND or if clause, so it's pretty close to thorough already. Thanks a ton.

Semicolon Over a year ago

since they said JS is preferred, translations of the above — contemporary: arr.filter((val, index, arr) => val === 0 && arr[index + 1] !== 0).length;, es5: arr.filter(function(val, index, arr) { return val === 0 && arr[index + 1] !== 0; }).length;

Collectives™ on Stack Overflow

Detecting Sequences of Zeroes in an Array

1 Answer 1

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related