we can take care of the duplicate entries, but then that would cost more space(int), as of now we are working with bool
On Mon, Jun 13, 2011 at 5:51 PM, sunny agrawal <sunny816.i...@gmail.com>wrote: > 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. > -- Regards, Arpit Sood -- 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.
