Link copied to clipboard. Share away!

Dissmis

Published on 09 Mar 2020

Program to check if the given arrays are disjoint is discussed here. Two arrays are said to be disjoint if they have no elements in common.

```
For example :
arr1 = {1,2,3,4,5}
arr2 = {6,7,8,9}
arr1 and arr2 elements are unique and hence they are said to be disjoint.
arr3 = {1,2,3,4,5}
arr4 = {4,5,6,7}
arr3 and arr4 are not disjoint as they have elements 4 and 5 in common.
```

This problem can be solved in four different ways.

**Method 1: **An easier approach is using two loops. Outer loop to traverse array 1 and an inner loop to check if any of the array 2 elements are found in array 1.

**Method 2: **This method uses sorting. The first array is sorted and the binary search is done for each element in array 2.

**Method 3: **The arrays are sorted and merge type of process is done to check if any of the array 2 elements are found in array 1.

**Method 4: **Firstly, the array 1 elements are inserted into a hash table. Secondly, the second array is traversed to check if any of the array 2 elements are found in array 1.

- Use two loops.
- Traverse the array 1 using the outer loop.
- Use the inner loop to check if the elements in array 2 are found in array 1.
- If at least one element of array 2 is found in array 1, return false. Else return true.

C

C++

Java

Python 3

Output

Input-
Enter the size of array 1 : 5
Enter the size of array 2 : 3
Input Array 1 elements: 1 2 3 4 5
Input Array 2 elements: 6 7 8
Output-
The arrays are disjoint

**Time complexity:** O(m * n)

- Sort the array 1.
- For every element in the array 2, perform binary search and find if the element is found in the sorted array.
- If any one element of array 2 is found in the sorted array, return false.
- Else return true.

C++ program to check if the given arrays are disjoint or not is discussed below.

C++

Output

Input-
Enter the size of array 1 : 5
Enter the size of array 2 : 3
Input Array 1 elements: 1 2 3 4 5
Input Array 2 elements: 6 7 8
Output-
The arrays are disjoint

**Time Complexity: **O(mLogm + nLogm) if quicksort has the best time complexity of mLogm.

If sorting is done at worst-case, then the time complexity will be O(m^2 + nLogm).

- Sort both the arrays.
- Use Merge type of process to see if any one element of sorted array 2 is found in sorted array 1.
- If any one element of sorted array 2 is found in sorted array 1, return false. Else, return true.

C++ program to check if the given arrays are disjoint or not using sorting and merging is given below.

C++

Output

Input-
Enter the size of array 1 : 5
Enter the size of array 2 : 3
Input Array 1 elements: 1 2 3 4 5
Input Array 2 elements: 6 7 8
Output-
The arrays are disjoint

**Time complexity: **O(mLogm + nLogn)

- Create a hash table.
- Traverse the first array and store the array elements in the hash table.
- Traverser the second array and check if any element is present in the hash table.
- If all the elements of array 2 are not found in array 1, return true. Else, return false.

C++ program to check if two given arrays are disjoint or not using hashing is discussed below

C++

Output

Time complexity: O(n)

*Recommended Programs*

If you have any feedback about this
article and want to improve this, please write to **enquiry@faceprep.in**

×