Solution for - all number appears two time except three number which appears 1 or 3 times. array indexing method is used to solve in O(n) time complexity and O(1).
first find min - O(n) then in for loop 1 to n a[abs(a[i])-min]=-a[abs(a[i])-min]; then find the -ve number in array then answer will be min + i ; (where i is -ve number index) all three number in array. All done in O(n) time complexity and O(1) space complexity. On Sun, Aug 12, 2012 at 10:38 PM, Daksh Talwar <[email protected]>wrote: > I guess O(1) extra space means constant extra space. > In that case, you can have a hash map ( or a bool array) and then switch > b/w true and false for every occurence. > All of those which havent been switched twice , are the result. > > > On Sun, Aug 12, 2012 at 9:16 PM, g4ur4v <[email protected]> wrote: > >> >> -- >> 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/-/La5cAv04gqQJ. >> 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?hl=en. >> > > > > -- > - - - - - - - - - - - - > With Regards > Daksh Talwar > > -- > 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?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 [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?hl=en.
