C++ program to determine the array is a subset of another array

Array is a subset of another array in C++

In this section we will determine the program to find if an Array is a subset of another array in C++ . If all the elements of array 2 are found in array 1, then array 2 is said to be a subset of array 1.

Here, we will discuss the following methods,

• Method 1 : Using nested loops
• Method 2 : Using sorting and binary search.
• Method 3 : Using sorting and merging.
• Method 4 : Using Set

Method 1 :

• Run a loop for loo from index 0 to length of arr2
• Run a inner loop from index 0 to length of arr2
• If(arr2[i]==arr1[j]), then break the inner loop
• Check if(j==m) then return 0.
• Otherwise, return 1.

Method 1 : Code in C++

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

bool isSubset(int arr1[], int arr2[], int m, int n)
{
int i = 0;
int j = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
if (arr2[i] == arr1[j])
break;
}

if (j == m)
return 0;
}

return 1;
}

// Driver code
int main()
{
int arr1[] = { 11, 10, 13, 21, 30, 70 };
int arr2[] = { 11, 30, 70, 10 };

int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);

if (isSubset(arr1, arr2, m, n))
cout<<"arr2[] is subset of arr1[] ";
else
cout<<"arr2[] is not a subset of arr1[]";

return 0;
}```

Output :

`arr2[] is subset of arr1[]`

Method 2 :

In this method we first sort arr1 then, using binary search we find the elements of arr2 in arr1

• Sort arr1[] using inbuilt sort function.
• For each element of arr2[], do binary search for it in sorted arr1[].
• If the element is not found then return 0.
• If all elements are present then return 1.

Method 2 : Code in C++

```#include
using namespace std;

int binarySearch(int arr[], int low, int high, int x);

bool isSubset(int arr1[], int arr2[], int m, int n)
{
int i = 0;

for (i = 0; i < n; i++) {
if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1)
return 0;

}
return 1;

}

int binarySearch(int arr[], int low,int high, int x) {
if (high >= low)
{
/*low + (high - low)/2;*/
int mid = (low + high) / 2;

if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x))
return mid;
else if (x > arr[mid])
return binarySearch(arr, (mid + 1), high, x);
else
return binarySearch(arr, low, (mid - 1), x);
}
return -1;
}

// Driver code
int main()
{
int arr1[] = { 11, 10, 13, 21, 30, 70 };
int arr2[] = { 11, 30, 70, 10 };

int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);

sort(arr1, arr1+m);
if (isSubset(arr1, arr2, m, n))
cout<<"arr2[] is subset of arr1[] ";
else
cout<<"arr2[] is not a subset of arr1[]";

return 0;
}```

Output :

`arr2[] is subset of arr1[]`

Method 3 :

• Sort both arrays: arr1[] and arr2[] using inbuilt sort function.
• Use Merging process to see if all elements of sorted arr2[] are present in sorted arr1[].

Method 3 : Code in C++

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

int binarySearch(int arr[], int low, int high, int x);

bool isSubset(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;

if (m < n)
return 0;

// Sort both the arrays
sort(arr1, arr1 + m);
sort(arr2, arr2 + n);

// Iterate till they donot exceed their sizes
while (i < n && j < m)
{

if (arr1[j] < arr2[i]) j++; else if (arr1[j] == arr2[i]) { j++; i++; } else if (arr1[j] > arr2[i])
return 0;
}

return (i < n) ? false : true;
}

// Driver code
int main()
{
int arr1[] = { 11, 10, 13, 21, 30, 70 };
int arr2[] = { 11, 30, 70, 10 };

int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);

if (isSubset(arr1, arr2, m, n))
cout<<"arr2[] is subset of arr1[] ";
else
cout<<"arr2[] is not a subset of arr1[]";

return 0;
}```

Output :

`arr2[] is subset of arr1[]`

Method 4 :

• Insert all the elements of arr1 in set data structure
• Iterate over arr2, and check if all its elements present in set, if yes then return trure
• Otherwise return false.

Method 4 : Code in C++

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

bool isSubset(int arr1[], int arr2[], int m, int n)
{
// Using STL set for hashing
set hashset;

// hset stores all the values of arr1
for (int i = 0; i < m; i++)
{
hashset.insert(arr1[i]);
}

// loop to check if all elements of arr2 also
// lies in arr1
for (int i = 0; i < n; i++) {
if (hashset.find(arr2[i]) == hashset.end())
return false;
}
return true;
}

// Driver code
int main()
{
int arr1[] = { 11, 10, 13, 21, 30, 70 };
int arr2[] = { 11, 30, 70, 10 };

int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);

if (isSubset(arr1, arr2, m, n))
cout<<"arr2[] is subset of arr1[] ";
else
cout<<"arr2[] is not a subset of arr1[]";

return 0;
}```

Output :

`arr2[] is subset of arr1[]`

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

One comment on “C++ program to determine the array is a subset of another array”

• Prashant

print(“Enter the first arr”)
arr1=list(map(int,input(“1st–>”).split()))
print(“Enter the second arr”)
arr2=list(map(int,input(“2nd–>”).split()))
flag=False
for i in arr1:
for j in arr2:
if j==i:
flag=True
else:
flag=False
if flag==True:
print(“arr 2 is subset of arr1”)
else:
print(“arr2 is not subset of arr1”)