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.
