Explore
ProGrad Programs
Placement Prep
TCS Codevita
Webinars
About Us

Edit
Reply




Edit

Check if the given arrays are disjoint in C, C++, Java and Python | FACE Prep

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.


Algorithm to check if the given arrays are disjoint


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


Program to check if the given arrays are disjoint


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)


Algorithm using sorting and binary search


  • 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).


Algorithm using sorting and merging


  • 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)


Algorithm using hashing


  • 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
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(n)


Recommended Programs





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