The 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 :nnarr1 = {1,2,3,4,5}narr2 = {6,7,8,9}nnarr1 and arr2 elements are unique and hence they are said to be disjoint.nnarr3 = {1,2,3,4,5}narr4 = {4,5,6,7}nnarr3 and arr4 are not disjoint as they have elements 4 and 5 in common.n
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.
@@coding::1@@
Time complexity: O(m * n)
C++ program to check if the given arrays are disjoint or not is discussed below.
@@coding::2@@
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).
C++ program to check if the given arrays are disjoint or not using sorting and merging is given below.
@@coding::3@@
Time complexity: O(mLogm + nLogn)
C++ program to check if two given arrays are disjoint or not using hashing is discussed below
@@coding::4@@
Time complexity: O(n)
Recommended Programs