How do I merge only unique numbers of two separate arrays?

Question

I really need help as this exercise is making me go crazy.

We have to merge two separate, sorted arrays. However, the third array can only contain numbers that are unique to each array, so if one number is in both arrays, it’s not allowed to show up.

I have been sitting here for days, I tried everything possible, but I literally can not think of a solution. I am really getting desperate. I know how to merge two sorted arrays, but I don’t know how I can only add the unique numbers.

Example:

a1 = (1, 2, 3, 4, 4, 4, 5, 5, 6)
a2 = (1, 4, 7, 9)

a3 = (2, 3, 5, 5, 6, 7, 9)

My code so far is as follows:

PROGRAM MergeArraysProgram;

PROCEDURE MergeArrays(a1: ARRAY OF INTEGER;
                      n1: INTEGER;
                      a2: ARRAY OF INTEGER;
                      n2: INTEGER;
                      VAR a3: ARRAY OF INTEGER;
                      VAR n3: INTEGER);
VAR
i: INTEGER;
j: INTEGER;

BEGIN

n3 := 0;
i := 0;
j := 0;

FOR i := 0 TO n1-1 DO BEGIN
    FOR j := 0 TO n2-1 DO BEGIN
        IF a2[j] = a1[i] THEN BEGIN
            a2[j] := a2[j+1];
        END;
    END;
END;


i := 0;
j := 0;


WHILE (i < n1) AND (j < n2) DO BEGIN
    IF a1[i] < a2[j] THEN BEGIN
        a3[n3] := a1[i];
        n3 := n3 + 1;
        i := i + 1;
    END;
    IF a1[i] > a2[j] THEN BEGIN
        a3[n3] := a2[j];
        n3 := n3 + 1;;
        j := j + 1;
    END;
    IF (i < n1) AND (j < n2) AND (a1[i] = a2[j]) THEN BEGIN
        i := i + 1;
        j := j + 1;
    END;
END;


WHILE (i < n1) DO BEGIN
    a3[n3] := a1[i];
    n3 := n3 + 1;
    i := i + 1;
END;

WHILE (j < n2) DO BEGIN
    a3[n3] := a2[j];
    n3 := n3 + 1;
    j := j + 1;
END;

END;

I can not think of anything anymore. My head already hurts, and I can’t really find anything for it online, at least I don't understand it or it has a entirely different context.

If anyone could give me a hint or help me I would really really appreciate it. I'm gonna lose my marbles

Answer 1

Since this is an exercise, you probably want the most effective solution. And since the input arrays are sorted, searching for each item from a1 in a2 and then doing the same for a2 is a huge waste of time.

The solution is actually fairly simple. Imagine having a pointer to each input array, both starting at the first element. Then you compare the items you currently point at, choose the one that's smaller, add it to the output array, and increment its pointer. If they are the same, you don't add anything to the output and you just have to increment each pointer until it points at a different number. That's it.

I think you can easily see that this is a correct solution if you try it on paper. The complexity of this is O(n1+n2). Here is a pseudocode:

i = 0 // pointer to a1
j = 0 // pointer to a2

while i < size(a1) || j < size(a2):
    // reached the end of a1, just add the rest of a2
    if (i >= size(a1)):
        a3.add(a2[j++])
    // reached the end of a2, just add the rest of a1
    else if (j >= size(a2)):
        a3.add(a1[i++])

    else if (a1[i] < a2[j]):
        a3.add(a1[i++])
    else if (a1[i] > a2[j]):
        a3.add(a2[j++])
    else:
        while (++i < size(a1) && a1[i] == a1[i-1])
        while (++j < size(a2) && a2[j] == a2[j-1])

I wanted to keep the last branch condensed, but if that's hard to understand, here is expanded version for a1:

i++ // move to the next item
while i < size(a1):
    // if the next item is different, we are done,
    // pointer now points at the first different item
    if a1[i] != a1[i-1]:
        break
    // otherwise increment pointer and try again
    else:
        i++

Answer 2

Here is a first problem in your algorithm :

IF (i < n1) AND (j < n2) AND (a1[i] = a2[j]) THEN BEGIN
        i := i + 1;
        j := j + 1;
    END;

as said earlier :

There are 3 cases when you know something is a duplicate: a1[i]=a2[j], a1[i]=a1[i+1], a2[j]=a2[j+1]. – Mark Ransom Commented yesterday

you're actually just assuming that the duplicate is the same time in both array. so here is the way to solve it :

so here, what you have to do is adding a new var , example :

var k : integer;
IF (i < n1) AND (j < n2) AND (a1[i] = a2[j]) THEN BEGIN
        k:= a1[i];
        while (k=a1[i]) do i+=1;
        while (k=a1[j]) do j+=1;
END;

your problem won't be solved , but I think it will help you solve it