@Siddhartha : doing bitwise addtiton may result into overflow if values are large..... correct me if i am wrong.
On Fri, Feb 17, 2012 at 10:04 AM, Siddhartha Banerjee < thefourrup...@gmail.com> wrote: > convert the numbers into base k... and do bitwise addition of numbers, > where > bit(a)+bit(b)=bit(a+b)mod(k) > of you convert all the numbers into base k and add them bitwise in a > variable say x, then the numbers occuring nk times vanish, and the final > result stored in x is a+a+....+a(b times) where a is the number repeating b > times... > next time go through the array again and see whether any number when added > with itself b times gives the same result as x, if yes, out put that number. > > I had seen a solution to a problem where in an array of size 3n+1, each > element except one repeating thrice, we need to find the non repeating > element in O(n) time O(1) space, i tried to generalize the proof to fit > this case... > > -- > 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. > -- 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.