Be the Class Topper with Video Lectures for Grade 6 to 12, JEE and NEET.

Book a session today

Clear Your Entrance Exams with Practice Tests and Mock Papers. 20% OFF

Book a session today

NEET, UPSC, TISS, CET, CAT, MBA Entrance Exam Practice Papers.

Book a session today

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

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

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.

C (/ˈsiː/, as in the letter c) is a general-purpose, procedural computer programming language supporting structured programming, lexical variable scope, and recursion, with a static type system. By design, C provides constructs that map efficiently to typical machine instructions.

 

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 program to check if the given arrays are disjoint

#include

#include

int disjoint_arrays(int arr1[], int arr2[], int n, int m)

{

int i,j;

for(i = 0;i

{

for(j=0;j

{

if(arr1[i] == arr2[j])

return -1;

}

}

return 1;

}

int main()

{

int m,n;

printf(“\nEnter the size of array 1 : “);

scanf(“%d”,&n);

printf(“\nEnter the size of array 2 : “);

scanf(“%d”,&m);

int arr1[n];

int arr2[m];

int i;

printf(“\nInput Array 1 elements : “);

for(i=0;i

{

scanf(“%d”,&arr1[i]);

}

printf(“\nInput Array 2 elements : “);

for(i=0;i

{

scanf(“%d”,&arr2[i]);

}

int res = disjoint_arrays(arr1,arr2,n,m);

if(res == -1)

printf(“\nThe arrays are not disjoint\n”);

else

printf(“\nThe arrays are disjoint\n”);

return 0;

}

 

C++

// C++ program to check if the given arrays are disjoint

#include

using namespace std;

int disjoint_arrays(int arr1[], int arr2[], int n, int m)

{

int i,j;

for(i = 0;i

{

for(j=0;j

{

if(arr1[i] == arr2[j])

return -1;

}

}

return 1;

}

int main()

{

int m,n;

cout << “Enter the size of array 1 : “;

cin >> n;

cout << “Enter the size of array 2 : “;

cin >> m;

int arr1[n];

int arr2[m];

int i;

cout << “\nInput array 1 elements : “;

for(i=0;i

{

cin >> arr1[i];

}

cout << “\nInput array 2 elements : “;

for(i=0;i

{

cin >> arr2[i];

}

int res = disjoint_arrays(arr1,arr2,n,m);

if(res == -1)

cout << “\nThe arrays are not disjoint\n”;

else

cout <<“\nThe arrays are disjoint\n”;

return 0;

}

 

JAVA

/ Java program to check if the given arrays are disjoint

import java.util.*;

class Main

{

static int disjoint_arrays(int arr1[], int arr2[], int n, int m)

{

int i,j;

for(i = 0;i

{

for(j=0;j

{

if(arr1[i] == arr2[j])

return -1;

}

}

return 1;

}

public static void main (String[] args)

{

int m,n,i;

int arr1[] = new int[10];

int arr2[] = new int[10];

Scanner sc = new Scanner(System.in);

System.out.print(“Enter the size of array 1 : “);

m = sc.nextInt();

System.out.print(“Enter the size of array 2 : “);

n = sc.nextInt();

System.out.print(“Input the array 1 elements : “);

for(i=0;i

{

arr1[i] = sc.nextInt();

}

System.out.print(“Input the array 2 elements : “);

for(i=0;i

{

arr2[i] = sc.nextInt();

}

int res = disjoint_arrays(arr1,arr2,n,m);

if(res == -1)

System.out.print(“\nThe arrays are not disjoint\n”);

else

System.out.print(“\nThe arrays are disjoint\n”);

}

}

 

PYTHON 3

# Python program to check if the given arrays are disjoint

def disjoint_arrays(arr1,arr2):

for i in range(0,len(arr1)):

for j in range(0,len(arr2)):

if(arr1[i] == arr2[j]):

return -1

return 1;

arr1 = [1,2,3,4,5]

arr2 = [6,7,8,9,10]

res = disjoint_arrays(arr1,arr2)

if(res == -1):

print(“The arrays are not disjoint”)

else:

print(“The arrays are disjoint”)

 

 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 discus

 

C++

// C++ program to check if the given arrays are disjoint or not using sorting and binary search

#include

using namespace std;

void swap(int *a, int *b)

{

int temp;

temp = *a;

*a = *b;

*b = temp;

}

int partition(int A[], int start, int end)

{

int x = A[end];

int i = (start – 1);

int j;

for (j = start; j <= end – 1; j++)

{

if(A[j] <= x)

{

i++;

swap(&A[i], &A[j]);

}

}

swap (&A[i + 1], &A[end]);

return (i + 1);

}

void quick_sort(int A[], int start, int end)

{

int pivot;

if(start < end>

{

pivot = partition(A, start, end);

quick_sort(A, start, pivot – 1);

quick_sort(A, pivot + 1, end);

}

}

int binary_search(int arr[], int low,

int high, int x)

{

if(high >= low)

{

int mid = (low + high)/2;

if(( mid == 0 || x > arr[mid-1]) && (arr[mid] == x))

return mid;

else if(x > arr[mid])

return binary_search(arr, (mid + 1), high, x);

else

return binary_search(arr, low, (mid -1), x);

}

return -1;

}

bool isSubset(int arr1[], int arr2[],int m, int n)

{

int flag = 1;

int i = 0;

quick_sort(arr1, 0, m-1);

for (i=0; i

{

if (binary_search(arr1, 0, m – 1,arr2[i]) == 1)

{

flag = 0;

break;

}

else

flag = 1;

}

return flag;

}

int main()

{

int m,n;

cout << “\nEnter the size of array 1 : “;

cin >> m;

cout << “\nEnter the size of array 2 : “;

cin >> n;

int arr1[m],arr2[n];

int i;

cout << “\nEnter the array 1 elements : “;

for(i=0;i

{

cin >> arr1[i];

}

cout << “\nEnter the array 2 elements : “;

for(i=0;i

{

cin >> arr2[i];

}

if(isSubset(arr1, arr2, m, n))

cout << “\nThe arrays are disjoint\n “;

else

cout << “\nThe arrays are not disjoint\n”;

getchar();

return 0;

}

 

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++

// C++ program to check if the given arrays are disjoint or not

#include

#include

using namespace std;

bool is_disjoint(int arr1[], int arr2[], int m, int n)

{

sort(arr1, arr1+m);

sort(arr2, arr2+n);

int i = 0, j = 0;

while (i < m>

{

if (arr1[i] < arr2>

i++;

else if (arr2[j] < arr1>

j++;

else

return false;

}

return true;

}

int main()

{

int m,n;

cout << “\nEnter the size of array 1 : “;

cin >> m;

cout << “\nEnter the size of array 2 : “;

cin >> n;

int arr1[m],arr2[n];

int i;

cout << “\nEnter the array 1 elements : “;

for(i=0;i

{

cin >> arr1[i];

}

cout << “\nEnter the array 2 elements : “;

for(i=0;i

{

cin >> arr2[i];

}

is_disjoint(arr1, arr2, m, n)? cout << “\nThe arrays are disjoint\n ” : cout << ” \nThe arrays are not disjoint\n”;

return 0;

}

 

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++

// C++ program to check if two given arrays are disjoint or not

#include

using namespace std;

bool is_disjoint(int arr1[], int arr2[], int n1, int n2)

{

set myset;

for (int i = 0; i < n1>

myset.insert(arr1[i]);

for (int i = 0; i < n2>

if (myset.find(arr2[i]) != myset.end())

return false;

return true;

}

int main()

{

int m,n;

cout << “\nEnter the size of array 1 : “;

cin >> m;

cout << “\nEnter the size of array 2 : “;

cin >> n;

int arr1[m],arr2[n];

int i;

cout << “\nEnter the array 1 elements : “;

for(i=0;i

{

cin >> arr1[i];

}

cout << “\nEnter the array 2 elements : “;

for(i=0;i

{

cin >> arr2[i];

}

if (is_disjoint(arr1, arr2, m, n))

cout << “\nThe given arrays are disjoint\n”;

else

cout << “\nThe given arrays are not disjoint\n”;

}

 

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)