Check whether an Array is subset of another Array
“Check whether an Array is subset of another Array” is a basic problem which can be solved using multiple methods like brute-force, sorting, binary search and hashing.
Here, in this problem, we are given two arrays; arr1 and arr2 and our task is to write a program to check whether arr2 is subset of arr1.
Note: There are no repetitions of elements in both the arrays.
Example:
Input:
Arr1 = {1, 2, 3, 4, 5}
Arr2 = {4, 5}
Output:
Arr2 is subset of Arr1
Input:
Arr1 = {7, 9, 4, 2, 6}
Arr2 = {4, 7, 3}
Output:
Arr2 is not a subset of Arr1
There are multiple methods to solve this problem. Here, in this post, we will discuss three of them.
Method 1: Brute-Force Approach
The simplest solution to check whether an array is subset of another array is that, for every element of Arr2, traverse Arr1 and check whether element of Arr2 is exists in Arr1 or not.
The time complexity of this solution is O(n*m), where ‘n’ and ‘m’ are size of two arrays.
C++ Program to Check whether an Array is subset of another Array is as follows:
/* C++ Program to Check whether an Array is subset of another Array */
#include<bits/stdc++.h>
using namespace std;
/* Function to Check whether an Array is subset of another Array */
void checkSubset(int Arr1[], int Arr2[], int size1, int size2)
{
/* Initializing Resultant Variable */
bool subset = true;
/* For Every Element of Arr2, linearly search in Arr1 */
for(int i = 0; i < size2; i++)
{
int temp = 0;
for(int j = 0; j < size1; j++)
{
if(Arr2[i] == Arr1[j])
{
temp = 1;
break;
}
}
if(temp == 0)
{
subset = false;
break;
}
}
/* Printing the Result */
if(subset)
{
cout<<"Arr2 is subset of Arr1";
}
else
{
cout<<"Arr2 is not a subset of Arr1";
}
}
int main()
{
int Arr1[] = {1, 2, 3, 4, 5};
int Arr2[] = {3, 1};
int size1 = sizeof(Arr1)/sizeof(Arr1[0]);
int size2 = sizeof(Arr2)/sizeof(Arr2[0]);
checkSubset(Arr1,Arr2,size1,size2);
}
Output: Arr2 is subset of Arr1
Method 2: Sorting and Binary Search
The steps required to check whether an Array is subset of another Array are as follows:
- Sort first array; Arr1.
- Now, for every element of second array, Arr2; search that element in Arr1 using Binary Search.
- If all the elements of second array are present in first array, then second array is subset of first array. Else, second array is not subset of first array.
The time complexity of this solution would be O(mlogm + nlogm), where ‘n’ and ‘m’ are respective size of array. “mlogm” is for sorting and “nlogm” is for binary search for every element of second array.
C++ Program to Check whether an Array is subset of another Array is as follows:
/* C++ Program to Check whether an Array is subset of another Array */
#include<bits/stdc++.h>
using namespace std;
/* Function to implement Binary Search */
bool binarySearch(int Arr[], int low, int high, int ele)
{
while(low <= high)
{
int mid = (low + high) / 2;
/* Check if middle element is ele */
if(Arr[mid] == ele)
return true;
/*
If middle element is greater than ele,
then, if ele is present, it must be present
in lower half of array
*/
if(Arr[mid] > ele)
high = mid - 1;
/*
If middle element is smaller than ele,
then, if ele is present, it must be present
in upper half of array
*/
else
low = mid + 1;
}
/* If ele is not present, return false */
return false;
}
/* Function to Check whether an Array is subset of another Array */
void checkSubset(int Arr1[], int Arr2[], int size1, int size2)
{
/* Initializing Resultant Variable */
bool subset = true;
/* Sort first Array */
sort(Arr1, Arr1 + size1);
/* For Every Element of Second Array, binary search in first array*/
for(int i = 0; i < size2; i++)
{
subset = binarySearch(Arr1, 0, size1-1, Arr2[i]);
if(subset == false)
{
break;
}
}
/* Printing the Result */
if(subset)
{
cout<<"Arr2 is subset of Arr1";
}
else
{
cout<<"Arr2 is not a subset of Arr1";
}
}
int main()
{
int Arr1[] = {1, 2, 3, 4, 5};
int Arr2[] = {3, 1};
int size1 = sizeof(Arr1)/sizeof(Arr1[0]);
int size2 = sizeof(Arr2)/sizeof(Arr2[0]);
checkSubset(Arr1,Arr2,size1,size2);
}
Output: Arr2 is subset of Arr1
Method 3: Hashing Based Approach
The steps required to check whether an Array is subset of another Array are as follows:
- Create a Hash set for all the elements of Arr1.
- Traverse Arr2 and for every element of Arr2, search Hash set.
- If all elements of Arr2 are present in Hash Set, then Arr2 is subset of Arr2, else, not.
The time complexity of this solution would be O(nlogm), where ‘n’ and ‘m’ are size of arrays and logm for searching in set.
C++ Program to Check whether an Array is subset of another Array is as follows:
/* C++ Program to Check whether an Array is subset of another Array */
#include<bits/stdc++.h>
using namespace std;
/* Function to Check whether an Array is subset of another Array */
void checkSubset(int Arr1[], int Arr2[], int size1, int size2)
{
/* Initializing Resultant Variable */
bool subset = true;
/* Create a Hash Set */
set <int> hashset;
/* Insert All Elements of Arr1 into hashset */
for(int i = 0; i < size1; i++)
{
hashset.insert(Arr1[i]);
}
/* For every Element of Arr2, search in hashset */
for(int i = 0; i < size2; i++)
{
if(hashset.find(Arr2[i]) == hashset.end())
{
subset = false;
break;
}
}
/* Printing the Result */
if(subset)
{
cout<<"Arr2 is subset of Arr1";
}
else
{
cout<<"Arr2 is not a subset of Arr1";
}
}
int main()
{
int Arr1[] = {1, 2, 3, 4, 5};
int Arr2[] = {3, 1};
int size1 = sizeof(Arr1)/sizeof(Arr1[0]);
int size2 = sizeof(Arr2)/sizeof(Arr2[0]);
checkSubset(Arr1,Arr2,size1,size2);
}
Output: Arr2 is subset of Arr1
Related Posts:
- Find Most Frequent Character of the String.
- Check Anagram Strings.
- Check Whether Given String is Palindromic Anagram or Not.
- Check Whether Given String is Panagram or Not.
- Find First Non-Repeating Character of the String.
- Find Most Frequent Element of the Array.
- Find Pair in an Array with Given Sum.
- Find First Repeating Element of an Array.
- Find Majority Element of an Array.
- Program to count total number of words in a string.
- Program to find smallest and largest word of the String.
- Program to find Most Frequent Character of the String.
- Program to Remove all the blank spaces from the String.
- Program to check if String is isogram or not.
- Program to Reverse Each word of the String.
- Program to Print All the Substring of the Given String.
- Program to find longest palindromic Substring.
- Program to check Anagram Strings.
- Program to check whether two Strings are Rotation of each other or not.
- Program to check Palindromic Anagram.
