CODEWITHSUNDEEP
calgorithmintegersequences
Gabriele Salvatori
Gabriele Salvatori

Reputation: 460

Counting sequences of k elements

If I have two arrays of integers:

a = {2,2,3,3,5,6,7,2,2,2}, b = {6,-5,2,2,2,2,4,5,3,3}

and an integer k = 2, which defines the number of sequences in succession (SAME in both arrays - [2,2], [3,3] , [2,2,2] in "a" / [2,2,2,2] , [3,3] in "b" ), how can I run a separate count for each sequence of numbers?

I thought the algorithm in this way:

int count = 1;  
for (int i=0; i<N; i++){
    if ( a[i] == a[i+1] && b[i] == b[i+1] && a[i] == b[i] ){
        count++;
    }

    if ( count >= k ){
        condition = true;
    }
}

Starting "count" by one for every sequence of elements could ensure that the count will be exact, but in this way, when checking the second and third position of the array a, it will also count the element 3 instead of stopping at 2.

Any suggestions?

Upvotes: 1

Views: 327

Answers (1)

anatolyg
anatolyg

Reputation: 28320

Seeing your comment "the function is boolean", I guess that you want to find out whether there is a sequence of identical numbers of length k or more, that is a sub-sequence of both input arrays.

It seems that the sub-sequence doesn't have to appear at the same position in both arrays (or else the exercise would be less interesting).

Assuming my guesses are right, you can use the following idea:

  1. Check all pairs of positions (p1,p2), where p1 is the position in the first array, and p2 is a position in the second array.
  2. Use the range 0...N-k for the positions, to avoid overflow (reading past the end of an array)
  3. For each pair of positions, check whether the k numbers starting at these positions are the same
  4. If they are the same for at least one pair of positions, the result is true; otherwise false

You can use two nested loops to implement (1) and (2), like so:

for (p1 = 0; p1 <= N - k; ++p1)
{
    for (p2 = 0; p2 <= N - k; ++p2)
    {
        ...
    }
}

You can use a separate function or a nested loop to check condition (3).

Upvotes: 2

Related Questions