Question

• Take advantage of the fact that the range of the integers in the list is fixed (0 to m, where m is the largest ID you can find in the linked list). Use a boolean array seen of length m+1 to indicate if elements in the array have been seen before. Then determine if there are duplicates by performing a single pass through the unsorted list. Hint: while traversing the list, seen[item] = True if integer item has been seen before in the search.
• 0
  1
  15
  112
  5000
• 150
  112
  5000

Answer 1

As you have not mentioned the language hence I am using C++
Below is the C++ code I hope that i have provided sufficient comments for your better understanding Note that I have done proper indentation but this code is automatically left alligned on this interface

#include<bits/stdc++.h>
using namespace std;
int main()
{
//number of elements in list
int n = 10;

//unsorted list
int arr[10] = {10, 34,65, 123,6, 12, 10, 43, 6};
cout<<"This is a list of input elements"<<endl;
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";

int maximum=arr[0];

//Find the maximum value from the array
for(int i=0;i<n;i++)
{
if(maximum<arr[i])
maximum=arr[i];
}

//Generate boolean array of size maximum+1
bool seen[maximum+1];

//Initialize seen array by false
for(int i=0;i<maximum+1;i++)
seen[i] = false;

cout<<endl<<"This is a list of all duplicate elements"<<endl;
//Traverse the list to check duplicate elements
for(int i=0;i<n;i++)
{
//This element is encountered for the first time
if(seen[arr[i]] == false)
seen[arr[i]] = true;

//This is a duplicate element has print it
else
cout<<arr[i]<<endl;
}
}

Below is the screenshot of output

I have tried to explain it in very simple language and I hope that i have answered your question satisfactorily.Leave doubts in comment section if any.