take an array of n elements.Initially all zero.Traverse the given array and mark the corresponding no as 1. At last traverse again and entr which is zero still is out Answer. Time -O(n) Space O(n) Thanks & Regards: Ankit Gupta
Marie von Ebner-Eschenbach<http://www.brainyquote.com/quotes/authors/m/marie_von_ebnereschenbac.html> - "Even a stopped clock is right twice a day." On Wed, Jul 29, 2009 at 6:26 AM, Channa Bankapur <[email protected]>wrote: > Here is a pseudocode for one of the solutions > > sumN = sum of all the elements of the arraysumN2 = sum of 1 to (n+2) > sumofXY = sumN2 - sumN /*sum of the interested integers, say x, y*/ > xorN = XOR of all the elements of the array > xorN2 = XOR of 1 to (n+2) > xorofXY = xorN XOR xorN2 /*XOR of x, y*/ > for i=1 to sumofXY/2 > if (xorofXY XOR i XOR (sumofXY-i)) is zero > then x is i, y is (sumofXY-i) > endfor > > > This solution has running time complexity of O(n) and needs constant extra > space. > > Thanks, > Channa > > > On Wed, Jul 29, 2009 at 5:57 PM, Ajinkya Kale <[email protected]>wrote: > >> use hashing. >> >> On Wed, Jul 29, 2009 at 4:50 PM, Vijayasarathy K >> <[email protected]>wrote: >> >>> >>> Consider an array of 'n' elements which contains all except 2 numbers >>> from 1....(n + 2). How can we find the 2 missing elements? >>> >>> >>> >> >> >> -- >> Ciao, >> Ajinkya >> >> >> >> > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
