// Two arrays x[0] < x[1]... and y[0] < y[1]... are given.

// Find the number of common elements in both arrays (that is, 

// the number of integers t such that t = x[ix] = y[iy] for some ix, iy). 

​

using System;

public class Program

{

    public static void Main()

    {

        int[] x = new int[] { 1, 3, 5, 7};

        int[] y = new int[] { 2, 4, 7, 8};

        int xi = 0, yi = 0, n = 0;

        // pre-condition: x[0]<...<x[x.Length-1] and y[0]<...<y[y.Length-1]

        // Definition: let's name x[0..xi-1] and y[0..yi-1] "processed elements"

        //             and all remaining elements "unprocessed elements"

        // invarint: n is the number of common elements among processed and 

        //      any unprocessed element exceeds any processed element and

        //      0<=xi<=x.Length and 0<=yi<=y.Length

        while (xi != x.Length && yi != y.Length)

        {

            if (x[xi] < y[yi])  // any other unprocessed element exceeds x[xi]

                xi++;

            else if (y[yi] < x[xi]) // any other unprocessed element exceeds y[yi]

                yi++;

            else // x[xi] = y[yi]

            {

                xi++;

                yi++;

                n++;

            }

        }

        // n is the number of common elements among processed

        // xi=x.Length or yi=y.Length => one of the arrays has no unprocessed elements =>

        // there is no common elements among unprocessed =>

        // n is the total number of common elements

        Console.WriteLine(n);

        // Time: xi+yi increased from 0 to x.Length+y.Length at max => O(x.Length+y.Length)

    }

}