Question

Hash Tables. In C programming language, solve these problems efficiently using Hashtables and analyze the running time of your solution.

1. Given an unsorted array of length N, print all elements that appear more than once.

2. Find the intersection of K unsorted arrays of N elements each. The intersection consists of elements that appear in all the K arrays.

Answer 1

code:(a)

#include <stdio.h>
int main() {
int n,i;
int a[100001];
for(i=0;i<100001;i++)a[i]=0;//intializing map array to 0
scanf("%d",&n);//accepting size of array
int array[n];
for(i=0;i<n;i++)
scanf("%d",&array[i]);//accepting elements of array
for(i=0;i<n;i++){
a[array[i]]++;//incrementing no of occurrence of array[i]
if(a[array[i]]==2)//if current element occurs for second time print it
printf("%d ",array[i]);}
   return 0;
}
//since the loop is to iterate array element once hence time complexity is o(size of array);

sample input/output:

code(b)

#include <stdio.h>
int main() {
int n,i,k,x,j;
int a[100001];
for(i=0;i<100001;i++)a[i]=0;//intializing map array to 0
scanf("%d%d",&k,&n);//accepting no of array and size of array
int b[n];//to store kth array element
for(j=1;j<=k;j++)
{
for(i=0;i<n;i++)
{
scanf("%d",&x);// input element of jth array
b[i]=x;
if(a[x]<(j*(j+1))/2)// hashing to find if x is present in array j
a[x]+=j;// increment hash value by j
}
}
for(i=0;i<n;i++)
if(a[b[i]]==(k*(k+1))/2)// element whose hash value is sum of first k natural numbers will be present in all k array
printf("%d ",b[i]);
   return 0;
}
//since the loop is to iterate array element once hence time complexity is o(sum of size of arrays)=o(k*n)

sample input/output:

please upvote if it was helpful.feel free to ask any related query.