Design an efficient data structure for representing a subset S of the integers f

Question

Design an efficient data structure for representing a subset S of the integers from 1 to n. The operations we wish to perform are these:

Select an integer i from the set and delete it.

Add an integer i to the set.

A mechanism must be provided to ignore a request to add integer i to S in the case where S alrady contains i. The data structure must be such that the time to select and delete an element and the time to add an element are constant and not dependent on ||S||, the size of S.

Analyze the time and space complexity of your algorithms.

Explanation / Answer

//We can use a hash table for the following representation
//Since the range is from 1 to n So we need to have a hash table of
// size n

Initialize the hash table by setting all indexes to 0

Whenever any number is inserted the value of that index is changed to 1

To delete a number
Check that index if number is present delete it otherwise print error message

To add an integer

Simply go to the location if it is zero then add the number and change it to 1
If number is already present just ignore

Time complexity = O(1)

Space Complexity = O(n)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.