For search O(n) ,then you can use array of fixed size & collision can be avoided by chaining using linked

list in this case worse case when all n elements maps to the same index , linear search will take O(n)

time to find the element. In order to get the O(1) search ,Create an array of size max( all a[i]) and then map each element corresponding to their index.