# Find similarities between two arrays.

Posted: 5 Mar, 2021

Difficulty: Easy

#### You have been given two arrays/list ‘ARR1’ and ‘ARR2’ consisting of ‘N’ and ‘M’ integers respectively. Your task is to return the number of elements common to ‘ARR1’ and ‘ARR2’ and the number of elements in the union of ‘ARR1’ and ‘ARR2’.

##### Example:

```
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.
```

##### Note:

```
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.
```

##### Input Format:

```
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’.
```

##### Output Format:

```
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’.
```

##### Note:

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

##### Constraints:

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

Approach 1

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’.

Approach 2

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’.

Approach 3

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

# Zero Pair Sum

Posted: 22 Jul, 2021

Difficulty: Moderate

# Longest Common Prefix

Posted: 24 Jul, 2021

Difficulty: Moderate

# Vertical Sum in BST

Posted: 27 Jul, 2021

Difficulty: Moderate

# Wildcard Queries

Posted: 31 Jul, 2021

Difficulty: Hard

# Matching Prefix

Posted: 21 Aug, 2021

Difficulty: Moderate