The objective of this project is to design and implement a (n) algorithm (using hash tables) to print exactly once the duplicate elements (the elements that appear more than once) in an array of integers. Use the code given for the hash table class (implemented using singly linked list) and the startup code for the main function to generate an array of integers. Test your code with the following values: array size: 20, maximum value for an integer: 10 and hash table size: 11. Implement the algorithm in the main function itself in the space provided. Note that your algorithm should print the duplicate elements only once. For example, the following is the output for an array of random integers generated and hashed with the above parameter values. Note that even though the (duplicate) integers 7, 6, 4, 2, 5 appear more than once, they are printed only once as part of the output for the elements that repeat.

Space complexity: You are free to use more than one hash table of the size input by the user for this problem.

(1) Complete code of the main function implementing the algorithm as well as the code for the Hashtable, Node and Singly Linked List classes.

(2) A report: explain the logic behind your algorithm (that it indeed finds duplicate elements and also prints them exactly once), provide a pseudo code of the algorithm and justify that the time complexity of the algorithm is (n). Assume the time complexity to search for the presence/absence of an element in a Hashtable is (1).

(3) Explain the purpose of each hash table used to accomplish the (n) time complexity.

(4) A screenshot of the output (similar to the sample provided above) of running your code for the main function after implementing the algorithm.

The code given for hashtable class is :

import java.util.*;

// implementing hash tables as an array of linked lists

class Node{

private int data;

private Node nextNodePtr;

public Node(){}

public void setData(int d){

data = d;

}

public int getData(){

return data;

}

public void setNextNodePtr(Node nodePtr){

nextNodePtr = nodePtr;

}

public Node getNextNodePtr(){

return nextNodePtr;

}

}

class List{

private Node headPtr;

public List(){

headPtr = new Node();

headPtr.setNextNodePtr(null);

}

public Node getHeadPtr(){

return headPtr;

}

public boolean isEmpty(){

if (headPtr.getNextNodePtr() == null)

return true;

return false;

}

public void insert(int data){

Node currentNodePtr = headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

while (currentNodePtr != null){

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr.getNextNodePtr();

}

Node newNodePtr = new Node();

newNodePtr.setData(data);

newNodePtr.setNextNodePtr(null);

prevNodePtr.setNextNodePtr(newNodePtr);

}

public void insertAtIndex(int insertIndex, int data){

Node currentNodePtr = headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != null){

if (index == insertIndex)

break;

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr.getNextNodePtr();

index++;

}

Node newNodePtr = new Node();

newNodePtr.setData(data);

newNodePtr.setNextNodePtr(currentNodePtr);

prevNodePtr.setNextNodePtr(newNodePtr);

}

public int read(int readIndex){

Node currentNodePtr = headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != null){

if (index == readIndex)

return currentNodePtr.getData();

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr.getNextNodePtr();

index++;

}

return -1; // an invalid value indicating

// index is out of range

}

public void modifyElement(int modifyIndex, int data){

Node currentNodePtr = headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != null){

if (index == modifyIndex){

currentNodePtr.setData(data);

return;

}

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr.getNextNodePtr();

index++;

}

}

public boolean deleteElement(int data){

Node currentNodePtr = headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

Node nextNodePtr = headPtr;

while (currentNodePtr != null){

if (currentNodePtr.getData() == data){

nextNodePtr = currentNodePtr.getNextNodePtr();

prevNodePtr.setNextNodePtr(nextNodePtr);

return true;

}

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr.getNextNodePtr();

}

return false;

}

public int countList(){

Node currentNodePtr = headPtr.getNextNodePtr();

int numElements = 0;

while (currentNodePtr != null){

numElements++;

currentNodePtr = currentNodePtr.getNextNodePtr();

}

return numElements;

}

public void IterativePrint(){

Node currentNodePtr = headPtr.getNextNodePtr();

while (currentNodePtr != null){

System.out.print(currentNodePtr.getData()+" ");

currentNodePtr = currentNodePtr.getNextNodePtr();

}

System.out.println();

}

public boolean containsElement(int data){

Node currentNodePtr = headPtr.getNextNodePtr();

while (currentNodePtr != null){

if (currentNodePtr.getData() == data)

return true;

currentNodePtr = currentNodePtr.getNextNodePtr();

}

return false;

}

}

class Hashtable{

private List[] listArray;

private int tableSize;

public Hashtable(int size){

tableSize = size;

listArray = new List[size];

for (int index = 0; index

listArray[index] = new List();

}

public int getTableSize(){

return tableSize;

}

public void insert(int data){

int hashIndex = data % tableSize;

listArray[hashIndex].insert(data);

}

public void deleteElement(int data){

int hashIndex = data % tableSize;

while (listArray[hashIndex].deleteElement(data));

}

public boolean hasElement(int data){

int hashIndex = data % tableSize;

return listArray[hashIndex].containsElement(data);

}

public void printHashTable(){

for (int hashIndex = 0; hashIndex

System.out.print("Hash Index: " + hashIndex + " : ");

listArray[hashIndex].IterativePrint();

}

}

}

class HashTableLinkedList{

public static void main(String[] args){

Scanner input = new Scanner(System.in);

int numElements;

System.out.print("Enter the number of elements you want to store in the hash table: ");

numElements = input.nextInt();

int maxValue;

System.out.print("Enter the maximum value for an element: ");

maxValue = input.nextInt();

int hashTableSize;

System.out.print("Enter the size of the hash table: ");

hashTableSize = input.nextInt();

Random randGen = new Random(System.currentTimeMillis());

int array[] = new int[numElements];

System.out.print("Elements generated: ");

for (int index = 0; index

array[index] = randGen.nextInt(maxValue);

System.out.print(array[index] + " ");

}

System.out.println();

// Use one or more hash tables and implement an algorithm

// to print the duplicate integers in the array exactly once

}

}

Enter the number of elements you want to store in the hash table: 20 Enter the maximum value for an element: 10 Enter the size of the hash table 11 Elements generated: ?564 2 3 7864709 426 65 26 Elements that repeat: ? 6 42 5