0

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

sova
  • 5,468
  • 10
  • 40
  • 48
  • 1
    What language are you using? – duncan Mar 21 '17 at 02:48
  • 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 Mar 21 '17 at 02:49
  • Would one zero surrounded by non-zeros considered a sequence? – Sash Sinha Mar 21 '17 at 02:49
  • 1
    @RossPresser I though LINQ was a slower than a for loop [due to increased overhead](https://stackoverflow.com/questions/14893924/for-vs-linq-performance-vs-future) – Bennett Yeo Mar 21 '17 at 02:50
  • @BennettYeo If you have enough elements in your array that the LINQ overhead really hurts your program's perceived responsiveness, then yes, avoid LINQ. If your program is doing anything else interesting at all, it probably doesn't even matter. – Ross Presser Mar 21 '17 at 02:54
  • @RossPresser C# would probably prefer a for loop solution since readability isn't really making much of a difference here... :) – Bennett Yeo Mar 21 '17 at 02:59
  • 1
    @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 Mar 21 '17 at 05:39

1 Answers1

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;
ruakh
  • 175,680
  • 26
  • 273
  • 307
  • Thanks, but the minimum length is 2 zeroes. How would we modify this to accommodate a new fact? – sova Mar 21 '17 at 05:47
  • 1
    @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. – ruakh Mar 21 '17 at 05:56
  • 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 Mar 21 '17 at 06:01
  • I believe a successful modification would need just another AND or if clause, so it's pretty close to thorough already. Thanks a ton. – sova Mar 21 '17 at 06:04
  • 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;` – Semicolon Mar 21 '17 at 06:11