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

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

#include <stdio.h>
#include <stdlib.h>

int disjoint_arrays(int arr1[], int arr2[], int n, int m)
{
int i,j;
for(i = 0;i<n;i++)
{
for(j=0;j<m;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<n;i++)
{
scanf(“%d”,&arr1[i]);
}
printf(“\nInput Array 2 elements : “);
for(i=0;i<m;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++ program to check if the given arrays are disjoint

#include <iostream>
using namespace std;

int disjoint_arrays(int arr1[], int arr2[], int n, int m)
{
int i,j;
for(i = 0;i<n;i++)
{
for(j=0;j<m;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<n;i++)
{
cin >> arr1[i];
}
cout << “\nInput array 2 elements : “;
for(i=0;i<m;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 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<n;i++)
{
for(j=0;j<m;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<n;i++)
{
arr1[i] = sc.nextInt();
}
System.out.print(“Input the array 2 elements : “);
for(i=0;i<m;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 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”)

 

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 tthe given arrays are disjoint or not is discussed below.

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

#include<bits/stdc++.h>

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<n; 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<m;i++)
{
cin >> arr1[i];
}
cout << “\nEnter the array 2 elements : “;
for(i=0;i<n;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;
}

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

#include<iostream>
#include<algorithm>
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 && j < n)
{
if (arr1[i] < arr2[j])
i++;
else if (arr2[j] < arr1[i])
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<m;i++)
{
cin >> arr1[i];
}
cout << “\nEnter the array 2 elements : “;
for(i=0;i<n;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;
}

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++ program to check if two given arrays are disjoint or not

#include<bits/stdc++.h>
using namespace std;

bool is_disjoint(int arr1[], int arr2[], int n1, int n2)
{
set<int> myset;

for (int i = 0; i < n1; i++)
myset.insert(arr1[i]);

for (int i = 0; i < n2; i++)
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<m;i++)
{
cin >> arr1[i];
}
cout << “\nEnter the array 2 elements : “;
for(i=0;i<n;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”;
}

Time complexity: O(n)

Output:

check if the given arrays are disjoint