// Two arrays x and y satisfying x[0]≤x[1]≤… and y[0]≤y[1]≤… are given. 

// Find the total number of different elements among x, y.

// Time: O(x.Length + y.Length), extra memory: O(1)

using System;

​

public class Program

{

    public static int CountDifferent(int [] x, int [] y)

    {

        if(0 == x.Length + y.Length)

            return 0;

​

        int count = 0;

        int ky = 0;

        int kx = 0;

        int last = 0;   // considered as "minus infinity" for zero count

        // Definition: we'll name the elements in segments x[0..kx-1] and y[0..ky-1] "processed" elements

        // Invariant: "count" different values are processed and

        //            each processed element is equal or smaller than each unprocessed element and

        //            if at least one element is processed then the biggest processed element is "last" and

        //            0 <= kx <= x.Length and 0 <= ky <= y.Length

        while(kx < x.Length || ky < y.Length)

        {

            int smallest;

            if(ky == y.Length || (kx < x.Length && x[kx] <= y[ky]))

            {

                smallest = x[kx];

                kx++;

            }

            else

            {   // ky < y.Length && (kx==x.Length || y[ky] < x[kx])

                smallest = y[ky];

                ky++;

            }

            // assert: last <= smallest

            if(0 == count || smallest > last)

            {

                count++;

                last = smallest;

            }

        }

        // count is the total number of different values in x and y

        return count;

    }

    public static void Test(int [] x, int [] y)

    {

        Console.WriteLine("Arrays {{{0}}} and {{{1}}} have {2} different values", 

                          string.Join(" ", x), string.Join(" ", y), CountDifferent(x, y));

    }

​

    public static void Main()

    {

        int [] empty = new int[0];

        Test(empty, empty);

        Test(empty, new[]{ 1, 2, 3});

        Test(new[]{ 1,3}, new[]{ 1, 2, 3});

        Test(new[]{ 1,1,1,1}, new[]{ 1});

        Test(new[]{ 1,1,1,1}, empty);

        Test(new[] { 1,4,7,9,12,45,56} , new[] {1,2,3,5,7,8,45,54,56,67});

    }

}