Question

Given two arrays: A[0..m-1] and B[0..n-1]. Find whether B[] is a subset of A[] or not. Both the arrays are not in sorted order. It may be assumed that elements in both array are distinct. Design an O(n) time algorithm that solves this problem. Provide pseudocode

Ex:
Input: A[] = {11, 1, 13, 21, 3, 7}, B[] = {11, 3, 7, 1}
Output: B[] is a subset of A[]

Input: A[] = {1, 2, 3, 4, 5, 6}, B[] = {1, 2, 4}
Output: B[] is a subset of A[]

Input: A[] = {10, 5, 2, 23, 19}, B[] = {19, 5, 3}
Output: B[] is not a subset of A[]

Answer 1

SOLUTION IN C LANGUAGE :

EXPLANATION: I have written the code along with explanation here I have used the concept of hashing where the data is stored in a format of key-value pair where key is unique for that in c I have used array, Based on the language you can use that, In java we have directly hash we can use that and do that .

Here for the convenience and checking for the exactness I have written code and checked that So I am directly passing the code so that it will be easier to understand.

NOTE: (int)( sizeof(B) / sizeof(B[0])) Don't worry about this, This is used to calculate the size of the array in c since there is no inbuilt function to determine size of the array.

SOLUTION CODE :

#include<stdio.h>

int main(){
   int A[]={11,1,13,21,3,7},B[]={11,3,7,1},i,subSet=0,sizeB=(int)( sizeof(B) / sizeof(B[0])),max=0;
   // sizeB here is used to calculate the size of b array("(int)( sizeof(B) / sizeof(B[0]))")
   //We are doing using hashing
   //Find the maximum element and then declare the array of that size
   for(i=0;i<(int)( sizeof(A) / sizeof(A[0]));i++){
       if(A[i]>max)
       max=A[i];
   }
   int c[max];
   //Declared array of size of max element
   //store the elements in the array of A to c based on the hashing
   //method of hashing is storing the data based on the value by applying some function to get the unique index here we have used
   //max number modular division n to get the unique index
   for(i=0;i<(int)( sizeof(A) / sizeof(A[0]));i++){
       c[A[i]%max]=A[i];
   }
   //While checking we need to again check that the given data is in the index of c array by again finding the index of B value in c
   //Array if it is there we will continue else we break and print the corresponding message
   for(i=0;i<sizeB;i++){
       if(B[i]==c[B[i]%max]){
           continue;
       }else{
           subSet=1;
           break;
       }
   }
   if(subSet==1){
       printf("B[] is not a subset of A[]");
   }else{
       printf("B[] is a subset of A[]");
   }
   return 0;
  
}

PSEUDO CODE:

Store the values of array A into a hash-based pattern

pass through the array B and check for the value in the hash-based array or object matched with the values of B array

if Matched

continue in checking for other values

else

break

print the message based on the condition of matching

SOLUTION IMAGE:

  

OUTPUT:

INPUT: A[]={11,1,13,21,3,7},B[]={11,3,7,1},

INPUT: A[]={11,1,13,21,3,7},B[]={11,3,7,19}