Suppose we are given two sequences A and B of n integers pos

Suppose we are given two sequences A and B of n integers, possibly contain- ing duplicates, in the range from 1 to 2n. Describe a linear-time algorithm for determining if A and B contain the same set of elements (possibly in different orders).

Solution

We can use count array to check whether they have same set of numbers in linear time

boolean isSameSet(int a[], int b[], int n){
  
   1. creating a count array of size 2n and initializing with zero
       int count[2n] = {0}

   2. traverse A and add count of each numbers in count array
       for i=1 to n do
           count[A[i]] = count[A[i]] + 1

   3. traverse B and check count of current number from B in count array
       if count is zero then they do not have same set of numbers
       else decrease count by 1 and process other element

       for j=1 to n do
           if count[B[j]] == 0
               return false
           else
               count[B[j]] =count[B[j]] -1

   4. Now, all elements of count array should be zero, if at least one of element is not zero, then they do
       not have same set
       for k=1 to 2n
           if count[k] != 0
               return fasle

   5. We reach here means they contaisn same set of numbers
       return true
}