Say I have a random circular array [1,1,1,0,0,1,1,1]. I want to check that there is a consecutive group of 5 or more 1s. The expected result is True because there are 6 1s in a row.

For [0,1,0,1,1,0,1,1] the expected result should be False because, even though there are 5 1s, they are not consecutive.

Pseudocode for my attempt looks like this:

Populate the array.
Copy the array into a queue.
Go through the array again.
If the first element is 0, enqueue(dequeue()) until a 1 is found.
If it is 1, enqueue(dequeue) until a 0 is found.
//Now any series of 1 should not be wrapped around
Go through the array a third time, keeping a tally of 1 and a tally of 0.
If the array starts on 1 and 0 is found before 5 1s, return false.
If the array starts on 0 and a 1 is found before a consecutive group of 3 0s, return false
Return true if a series of 5 1s is found.
Return true if a series of 3 Os is found AND there are not more Os in the array.

Anyways it sometimes doesn't work. It is confusing. And it goes through the array 3 times.

How do you solve this in O(n) or better? ...Or at least in a way that works?

CodePudding user response：

It should be enough to go through the array at most twice.

You can iterate through it with an index between 0 and 2n-1. For the array accesses, you apply a modulo of n to your index to make sure you stay within bounds.

While iterating, you increment a counter on every 1 you see, and reset it on a 0. If your counter reaches 5, you return true. Otherwise, you return false after you're done with the iteration. Additionally, you can immediately return false if you observe a 0 in the second half of the iteration.

Code example:

// a is the input array

// If input size is variable; can be removed for fixed input sizes >= 5
if (a.length < 5) {
    return false;
}

int counter = 0;
for (int i = 0; i < 2 * a.length; i  ) {
    if (a[i % a.length] == 1) {
        if (  counter >= 5) return true;
    } else if (i >= a.length) {
        return false;
    } else {
        counter = 0;
    }
}
return false;

CodePudding user response：

You can use this procedure:

• Find the index of the first zero.

• If there is no zero:

  • If the size of the array >= 5 return true
  • Else return false

• Set the counter (of consecutive 1) to zero

• Starting from the index found in the first step, perform as many iterations as the size of the array:

  • If the array has a 1 at the current index increment the counter, and if now the counter is 5 return true
  • If the array has a 0 at the current index, reset the counter to 0
  • Increment the index
  • If the index is equal to the array size, make it 0 (wrap around)
  • If the index is equal to the index found in the first step (where the first 0 is), then return false

Here is a little implementation in JavaScript:

function hasFiver(arr) {
    const n = arr.length;
    let i = arr.indexOf(0);
    if (i == -1 || i >= 5) return (n >= 5);
    
    let counter = 0;
    for (let j = i   1; j != i; j = (j   1) % n) {
        if (arr[j] == 1) {
            counter  ;
            if (counter >= 5) return true;
        } else {
            counter = 0;
        }
    }
    return false;
}

// I/O handling
const input = document.querySelector("input");
const output = document.querySelector("div");
input.addEventListener("input", refresh);

function refresh() {
    const arr = this.value.match(/[01]/g)?.map(Number) ?? [];
    output.textContent = hasFiver(arr);
}
refresh.call(input);

Input array: <input value="1 1 1 1 0 0 1 1 0 1">
<div></div>

CodePudding user response：

I will try to approach this problem with Python groupby in itertools lib:

It will go through the list only once, but with the cost of more space.

from itertools import groupby

circular = [1,1,1,0,0,1,1,1]

def any_consecutive(seq):
    for k, g in groupby(seq   seq):   # because it's circular...
        yield (k, len(list(g)))


if __name__ == '__main__':
    series = 3
    
    print(list(any_consecutive(circular))) # all num and series in tuples

    #
    print(any(count >= series for _, count in any_consecutive(circular)))  # True
    print(any(count >= 7 for _, count in any_consecutive(circular)))  # False