a)You are given a sequence S of n integers each within range [0..n]. Give the pseudocode for an O(n) algorithm that checks if S contains equal elements, and returns a sequence of those elements that appear in S at least twice.

b) [3 pts] Explain why your algorithm runs in O(n) time.

c) [3 pts] Also explain the space requirement of your algorithm (other than the input sequence S), and remember that the time required cannot be less than the space required. d) [16 pts]

d)Now answer the same questions as above, but there is no restriction that all elements are within range [0..n]. You are allowed to run in expected O(n) time. Write down any assumptions you make.