Let A = {a_1, a_2, ..., a_n} and B = {b_1, b_2, ..., b_m} be two (unordered!) ar

Question

Let A = {a_1, a_2, ..., a_n} and B = {b_1, b_2, ..., b_m} be two (unordered!) arrays of numbers that don't contain duplicates. Consider the problem of finding their symmetric difference (all items that are an element of one array without being an element of both arrays). Give pseudocode for a brute-force algorithm for solving this problem and determine its efficiency class. Give pseudocode for a presorting-based algorithm for solving this problem and determine its efficiency class. You can assume an implementation of whichever sorting algorithm you want exists.

Explanation / Answer

Considering two Arrays A of size m and B of Size n:

When the Arrays are unordered:

When the Arrays are ordered:

PseudoCode for Unsorted Arrays:

findSymmetricDiff(A[m], B[n]) :

                Hashmap<Integer> map;
List<Integer> result;

                For i=1 to n
Push B[i] on map;

                For i=1 to m
If(A[i] is not present in map)
List.add(A[i])

Output List.

You can use the algo given above for any kind of Array, either sorted or unsorted.

PseudoCode for presorting algo:

findSymmetricDiff(A[m], B[n]) :

                List<Integer> result;

                Sort(B); // assuming sort algorithm is in place

                For i=1 to m
If(binary_search(A[i], B) == -1)
List.add(A[i])

Output List.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.