Find if an array is a subset of another array in C, C++, Java and Python

Select Articles

Find if an array is a subset of another array in C, C++, Java and Python

Program to find if an array is a subset of another array is discussed here. If all the elements of array 2 are found in array 1, then array 2 is said to be a subset of array 1.

 

For example,

arr1 = {1,2,3,4,5}

arr2 = {3,4,5}

arr2 is a subset of arr1.

arr3 = {1,2,3,4,5}

arr4 = {1,2,9}

arr4 is not a subset of arr3.

This problem can be solved in four different ways.

 

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

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 the array 2 elements are found in array 1.

Method 4: Firstly, the array elements are inserted into a hash table. Secondly, the second array is traversed to check the number of occurrence of each element of array 2 in array 1.
 

Algorithm to check if an array is a subset of another array

Use two loops.

Traverse the array using the outer loop.

Using the inner loop, check if the elements in array 2 are present in array 1.

If all the elements of array 2 are found in array 1, return true.

Else, return false.

 

Program to check if an array is a subset of another array

C

// C program to check if an array is a subset of another array

#include

bool isSubset(int arr1[], int arr2[],

int m, int n)

{

int i = 0;

int j = 0;

for (i = 0; i < n>

{

for (j = 0; j < m>

{

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

break;

}

if (j == m)

return 0;

}

return 1;

}

int main()

{

int m,n;

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

scanf(“%d”, &m);

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

scanf(“%d”, &n);

int arr1[m],arr2[n];

int i;

printf(“\nEnter the array 1 elements : “);

for(i=0;i

{

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

}

printf(“\nEnter the array 2 elements : “);

for(i=0;i

{

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

}

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

printf(“\nArray2 is a subset of Array1\n “);

else

printf(“\nArray2 is not a subset of Array1\n”);

getchar();

return 0;

}

 

C++

// C++ program to check if an array is a subset of another array

#include

using namespace std;

bool isSubset(int arr1[], int arr2[],

int m, int n)

{

int i = 0;

int j = 0;

for (i = 0; i < n>

{

for (j = 0; j < m>

{

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

break;

}

if (j == m)

return 0;

}

return 1;

}

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 << “\nArray2 is a subset of Array1\n “;

else

cout << “\nArray2 is not a subset of Array1\n”;

getchar();

return 0;

}

 

JAVA

// Java program to check if an array is a subset of another array

import java.util.*;

class Main

{

static boolean subset_arrays(int arr1[], int arr2[],

int m, int n)

{

int i = 0;

int j = 0;

for (i = 0; i < n>

{

for (j = 0; j < m>

{

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

break;

}

if (j == m)

return false;

}

return true;

}

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();

}

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

System.out.print(“\nArray 2 is a subset of array 1\n”);

else

System.out.print(“\nArray 2 is not a subset of array 1\n”);

}

}

 

PYTHON 3

# python program to check if an array is a subset of another

def disjoint_arrays(arr1,arr2):

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

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

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

break

if(j == len(arr2)):

return 0

return 1;

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

arr2 = [3,4,5]

res = disjoint_arrays(arr1,arr2)

if(res == 1):

print(“Array 2 is a subset of array 1”)

else:

print(“Array 2 is not a subset of array 1”)

 

Output

Input- Enter the number of elements in array 1:5 Enter the elements of array 1: 1 2 3 4 5 Enter the number of elements in array 2:3 Enter the elements of array 2:3 4 5 Output- Array 2 is a subset of Array 1

 

Time Complexity: O(m*n)

 

Algorithm using sorting and binary search

Sort the array 1 elements.

For every element in the array, perform binary search and find if the element is found in the sorted array.

If all the elements of the array are found in the sorted array, return true.

Else return false.

 

C++ program to check if an array is a subset of another using sorting and binary search is given below

 

C++

// C++ program to check if an array is a subset of another array

#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 i = 0;

quick_sort(arr1, 0, m-1);

for (i=0; i

{

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

return 0;

}

return 1;

}

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 << “\nArray2 is a subset of Array1\n “;

else

cout << “\nArray2 is not a subset of Array1\n”;

getchar();

return 0;

}

 

Output

Input- Enter the number of elements in array 1:5 Enter the elements of array 1: 1 2 3 4 5 Enter the number of elements in array 2:3 Enter the elements of array 2:3 4 5 Output- Array 2 is a subset of Array 1

 

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 all elements of the sorted array are found in sorted array 1.

If all the elements of array 2 are found in array 1, return true. Else, return false.

C++ program to check if an array is a subset of another array using sorting and merging is given below .

 

C++

#include

using namespace std;

int main() 

{

   // Try out your code here

    cout << "Hello, World!";

    return 0;#include

using namespace std;

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

{

int i = 0, j = 0;

if (m < n>

return 0;

sort(arr1, arr1 + m);

sort(arr2, arr2 + n);

while (i < n>

{

if( arr1[j]

j++;

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

{

j++;

i++;

}

else if( arr1[j] > arr2[i] )

return 0;

}

return (i < n>

}

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 << “\nArray2 is a subset of Array1\n “;

else

cout << “\nArray2 is not a subset of Array1\n”;

getchar();

return 0;

}

}

 

Output

Input- Enter the number of elements in array 1:5 Enter the elements of array 1: 1 2 3 4 5 Enter the number of elements in array 2:3 Enter the elements of array 2:3 4 5 Output- Array 2 is a subset of Array 1

 

Time complexity: O(mLogm + nLogn)

 

Algorithm using hashing

Create two hash tables for array 2 and array 1 where the value of the arrays will be stored in column 1 and their the count of each value will be stored in column 2 in the table.

Traverse the second array and check the number of occurrence of each element of array 2 in array 1.

If the number of occurrences is same, then return true else return false.

C++ program to check if an array is a subset of another using hashing is discussed below

 

C++

// C++ program to check if an array is a subset of another array using hashing

#include

#include

using namespace std;

unordered_map map1;

unordered_map map2;

int isSubset(int n2,int array2[])

{

for(int i=0;i

{

if(!map1[array2[i]])

{

return 0;

}

}

return 1;

}

int main()

{

int arr1[10],arr2[10],n1,n2;

map1.reserve(10);

map2.reserve(10);

printf(“\nEnter the number of elements in array 1: “);

scanf(“%d”,&n1);

printf(“\nEnter the elements of array 1: \n”);

for(int i=0;i

{

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

map1[arr1[i]]++;

}

printf(“\nEnter the number of elements in array 2: “);

scanf(“%d”,&n2);

printf(“\nEnter the elements of array 2:\n”);

for(int i=0;i

{

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

map2[arr2[i]]++;

}

if(isSubset(n2,arr2))

{

printf(“\nArray 2 is a subset of Array 1\n”);

}

else

{

printf(“\nArray 2 is not a subset of Array 1\n”);

}

return 0;

}

 

Output

Input- Enter the number of elements in array 1:5 Enter the elements of array 1: 1 2 3 4 5 Enter the number of elements in array 2:3 Enter the elements of array 2:3 4 5 Output- Array 2 is a subset of Array 1