that will report duplicate entries multiple times :( On Mon, Jun 13, 2011 at 5:38 PM, sunny agrawal <sunny816.i...@gmail.com>wrote:
> 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 <divyekap...@gmail.com>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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 > > -- 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
