New update is available. Click here to update.

Last Updated: 5 Mar, 2021

Difficulty: Easy

```
Let’s assume ‘ARR1’ is [1,2,3,4,5] and ‘ARR2’ is [2,4,6,8]. Elements common to ‘ARR1’ and ‘ARR2’ are [2,4] as they occur in both ‘ARR1’ and ‘ARR2’. Therefore the number of elements common to ‘ARR1’ and ‘ARR2’ is 2. Union of ‘ARR1’ and ‘ARR2’ is [1,2,3,4,5,6,8]. Therefore the number of distinct elements in the union of ‘ARR1’ and ‘ARR2’ is 7. So, the answer will be 2 7.
```

```
1. ‘ARR1’ consists of distinct integers i.e no number occurs twice in array/list.
2. ‘ARR2’ consists of distinct integers i.e no number occurs twice in array/list.
```

```
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains two single space-separated integers ‘N' and ‘M’ representing the size of the array/list ‘ARR1’ and ‘ARR2’ respectively.
The second line of input of each test case contains ‘N’ single space-separated integers representing the array/list elements of ‘ARR1’.
The third line and the last line of input of each test contains ‘M’ single space-separated integers representing the array/list elements of ‘ARR2’.
```

```
For each test case, return the number of elements common to ‘ARR1’ and ‘ARR2’ and the number of distinct elements in the union of ‘ARR1’ and ‘ARR2’.
```

```
You do not need to print anything; it has already been taken care of. Just implement the function.
```

```
1 <= T <= 10
1 <= N <= 1000
1 <= M <= 1000
1 <= ‘arr1[i]’ <= 10^5
1 <= ‘arr2[i]’ <= 10^5
Time Limit: 1sec
```

We will declare ‘INTERSECTION_SIZE = 0’ which stores the number of common elements in ‘arr’ and ‘brr’.

- For each element in ‘ARR1’ we will iterate ‘ARR2’ and check if it is present in ‘ARR2’
- If ‘ARR1[i]’ is present in ‘ARR2’ increase ‘INTERSECTION_SIZE’ by 1.
- After calculating ‘INTERSECTION_SIZE’ we can calculate ‘UNION_SIZE’ as 'N' + 'M' - ‘INTERSECTION_SIZE’ because each element in the intersection was counted twice , therefore we will decrease the total number of elements i.e. 'N' + 'M' by ‘INTERSECTION_SIZE’.
- Return ‘INTERSECTION_SIZE’ and ‘UNION_SIZE’.

We will declare ‘INTERSECTION_SIZE = 0’ which stores the number of common elements in ‘ARR1’ and ‘ARR2’.

- Sort array/list ‘ARR1’ and ‘ARR2’.
- Since ‘ARR2’ is sorted we can do binary search.
- For each element in ‘ARR1’ we will do binary search in ‘ARR2’ and check if it is present in ‘ARR2’. If it is present in ‘ARR2’ increase ‘INTERSECTION_SIZE’ by 1.
- After calculating ‘INTERSECTION_SIZE’ we can calculate ‘UNION_SIZE’ as 'N' + 'M' - ‘INTERSECTION_SIZE’ because each element in the intersection was counted twice , therefore we will decrease the total number of elements i.e. 'N' + 'M' by ‘INTERSECTION_SIZE’.
- Return ‘INTERSECTION_SIZE’ and ‘UNION_SIZE’.

We will declare ‘INTERSECTION_SIZE = 0’ which stores the number of common elements in ‘ARR1’ and ‘ARR2’.

- Map all the elements of ‘ARR1’ in an unordered map with map-value 1.
- For each element in ‘ARR2’ check if it is present in map. If it is present in map increase ‘INTERSECTION_SIZE’ by 1.
- After calculating ‘INTERSECTION_SIZE’ we can calculate ‘UNION_SIZE’ as 'N’ + 'M' - ‘INTERSECTION_SIZE’ because each element in the intersection was counted twice , therefore we will decrease the total number of elements i.e. 'N’ + 'M' by ‘INTERSECTION_SIZE’.
- Return ‘INTERSECTION_SIZE’ and ‘UNION_SIZE’.

SIMILAR PROBLEMS

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Search In A Sorted 2D Matrix

Posted: 23 Nov, 2022

Difficulty: Moderate

Maximum GCD

Posted: 8 Dec, 2022

Difficulty: Hard

Sort 0s, 1s, 2s

Posted: 24 Dec, 2022

Difficulty: Easy

Fake Coin Problem

Posted: 24 Dec, 2022

Difficulty: Easy

Popular Interview Problems: