We have M+N) memory space and each number X<=N. So it's ok to use such counting array.
On Nov 4, 11:45 am, ankit agarwal <[email protected]> wrote: > Hi, > > What will happen if the numbers are 1,10000,10001,10002 etc.. > then you will lot of memory. > > On Nov 4, 11:41 am, Naveen Kumar <[email protected]> wrote: > > > > > > > > > Hi, > > > If we don't have to preserve the order than, > > > a[1...N] can be used and if we have input like 1,4,3,6 > > > Insertion can be done as > > a[1]++, a[4]++, a[3]++, a[6]++ > > > and deletion using a[1]--- and so on. > > > searching is also using a[X]. > > > On Thu, Nov 4, 2010 at 11:18 AM, jagannath <[email protected]> wrote: > > > > Design a data structure that allows one to search, insert, and delete > > > an integer X in O (1) time in a table (i.e. constant time, independent > > > of the total number of integers stored). Assume that 1≤X≤N. Also > > > assume that the maximum number of integers in the table can only be M > > > at any one time. You are given M+N units of space available for the > > > table. > > > > -- > > > You received this message because you are subscribed to the Google Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]<algogeeks%2bunsubscr...@googlegroups > > > .com> > > > . > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > -- > > Cheers > > Naveen Kumar -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
