Algorithm to find the number of common elements in two sorted arrays.

Here's an algorithm to find the number of common elements in two sorted arrays:

1. Initialize two pointers, `ptr1` and `ptr2`, to the start of both arrays, respectively.

2. Initialize a variable `count` to 0 to keep track of the number of common elements.

3. While `ptr1` is less than the length of the first array and `ptr2` is less than the length of the second array, do the following steps:

     - If the element at `arr1[ptr1]` is equal to the element at `arr2[ptr2]`, increment `count` by 1, and move both pointers forward by 1.

     - If the element at `arr1[ptr1]` is less than the element at `arr2[ptr2]`, move `ptr1` forward by 1.

     - If the element at `arr1[ptr1]` is greater than the element at `arr2[ptr2]`, move `ptr2` forward by 1.

4. Return the value of `count` as the number of common elements.

Here's a sample implementation in Python:

```python

def count_common_elements(arr1, arr2):

    ptr1 = 0

    ptr2 = 0

    count = 0


    while ptr1 < len(arr1) and ptr2 < len(arr2):

        if arr1[ptr1] == arr2[ptr2]:

            count += 1

            ptr1 += 1

            ptr2 += 1

        elif arr1[ptr1] < arr2[ptr2]:

            ptr1 += 1

        else:

           ptr2 += 1

    return count

```

You can call this function by passing in your sorted arrays as arguments:

```pythonarray1 = [1, 3, 4, 6, 7, 9]

array2 = [2, 3, 5, 6, 8, 9]

common_count = count_common_elements(array1, array2)

print("Number of common elements:", common_count)

```

This will output:

Number of common elements: 3

In the example above, the common elements between `array1` and `array2` are 3, 6, and 9, resulting in a count of 3.

Post a Comment

Previous Post Next Post

Ads

Ad