Finding a consecutive group of n elements in a circular array

user_2014878 0
Viewed 61

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?

search algorithm
3 Answers

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;
user_24751760

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>

user_54598390

This approach takes just 1 and a bit passes, but better yet does its best to skip through the array. If the array has random 1s and 0s, then the expected running time is O(n/k). It does that by skipping k ahead of where it has been, and if it landed on a 1 then it figures out how long a stretch of 1s it landed on. If it is too short, it jumps ahead again.

This would be much simpler using the modulo operator, but the modulo operator is expensive relative to everything else.

def has_1s(array, k):
    if 0 == k:
        return True
    elif len(array) <= k:
        # Trivial version.
        for x in array:
            if x != 1:
                return False
        return True
    else:
        high = -1
        high_wrap = False
        while not high_wrap:
            high += k
            if len(array) <= high:
                high_wrap = True
                high -= len(array)
            if array[high] == 1:
                low = high
                low_wrap = False
                while 1 == array[low]:
                    low -= 1
                    if low < 0:
                        if high_wrap:
                            low += len(array)
                            low_wrap = True
                        else:
                            break
                if low_wrap:
                    low -= len(array)

                while high < low + k and 1 == array[high]:
                    high += 1
                    if len(array) <= high:
                        high -= len(array)
                        high_wrap = True
                        low -= len(array)
                        low_wrap = True
                if k <= high - lower:
                    return True
        return False
user_5854110
Related