Data Structures and Algorithms I
Exercise 1


3. Carefully design an algorithm that takes as parameters two integer arrays A and B
and creates and returns a new integer array containing all elements that are found in
either array A or B (i.e., their union). Each element should appear in the resulting array
only once, even if it appears multiple times in both input arrays or in either of them. Do
not use built-in set types or their operations, and do not modify the input arrays or their
contents. First, draw a diagram of the problem, then write down the solution principle
clearly in English. After this, begin refining the solution principle into a more precise
algorithm in 1-3 steps so that the final solution principle is described very precisely and
can be mechanically converted into a working subroutine (programming language). What
is the time complexity of your algorithm? Could it be improved?

Illustration: A: [5 4 2 4], B: [1 6 2] -> Result: [5 4 2 1 6]

Version 1:
Create a new result array C. Go through each element of array
A one by one and check if the element is already in array C. If it is
not found, add the element to the result array. Do the same for array B.

Version 2:
Create a result array C (of size ??)
For each element x in array A, do the following:
	Check if x is in array C
		If found:
			Do nothing
		If not found:
			Add x to the result array
For each element x in array B, do the following:
	Check if x is in array C
		If found:
			Do nothing
		If not found:
			Add x to the result array
Return the result array

Version 3:

temp_result = new array (size equal to the total size of A and B)
result_count = 0
For each element x in array A, do the following:
	found = false
	For each element y in array C, do the following:
		If x is the same as y
			found = true, stop the inner loop
	If found is false
		Set x at position result_count in the temp result array
		result_count = result_count + 1
For each element x in array B, do the following:
	found = false
	For each element y in array C, do the following:
		If x is the same as y
			found = true, stop the inner loop
	If found is false
		Set x at position result_count in the temp result array
		result_count = result_count + 1

Create a new final result array with size result_count
Copy the first result_count elements from the temp result array to the final result array.
Return the final result array

Version 4:
Clarification on copying the final result array:
result = new array (of size result_count)
for i = 0..result_count-1:
	final_result_array[i] = temp_result[i]

Time complexity: O((|A|+|B|)^2) (product of the number of elements in
the arrays). As the course progresses, we will learn a more efficient
way to determine if an element x is in array B, which will reduce the
time complexity to O(|A| + |B|), making it significantly more efficient
if the arrays are large.