why do we need 2 bits at all ?? i think single bit per table entry will do. say table is T[1025], and array is A[M]
1. Go through the N sized array and set bit 0 of the hash table entry to 1 if it is present in the first array. 2. Go through the M sized array and if T[a[i]] is set then this element is there in second array else not. any cases this can fails?? On Mon, Jun 13, 2011 at 5:28 PM, Divye Kapoor <[email protected]> wrote: > Use a hash table of size 1025 with bits per table entry = 2. > 1. Go through the N sized array and set bit 0 of the hash table entry to 1 > if it is present in the first array. > 2. Go through the M sized array and set bit 1 of the hash table entry to 1 > if the element belongs to 0 to 1024. > 3. Go through the hash table and print entries with bit values 11. > > Space usage = O(1), 2050 bits (rounded off to the corresponding nearest > byte). Time complexity = O(N + M) > > -- > DK > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/xP98wCgLEAwJ. > > 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. > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.
