I dint understand answer to rotation question. Also is there any way of identifying duplicates in an array without using any extra memory (like creating hash table takes extra memory).
Any reference w.r.t book (or google book) to seek the concept behind two questions? Please let me know. Regards, Vikas J On Sat, Jul 3, 2010 at 12:47 PM, Abhirup Ghosh <[email protected]> wrote: > How can you find smallest element in the array in O(logn) time? Can > you please elaborate? > > -Abhirup > > > > On Fri, Jul 2, 2010 at 3:44 PM, jalaj jaiswal <[email protected]> > wrote: > > second question can be done in O(logn) > > do a modified binary search to find the starting index of the rotated > array > > i.e the smallest element. > > > > after that you have two sorted arrays.. > > for eg 789 1236 (your modified binary search should return index of 1) > > now check if the elemnent you are searching in greater then a[min] then > do > > binary search in 1st array > > else do in second array > > > > > > > > > > On Fri, Jul 2, 2010 at 3:29 PM, Abhirup Ghosh <[email protected]> > wrote: > >> > >> 1. (1) Maintain a hash table and insert the elements in the table when > >> passing through the array. And if there is a collision then that > >> element is a duplicate element in the array.Time - O(n) and the space > >> is O(n). > >> (2) Duplicate is detected by the above process. Then it can be easily > >> removed. I can't get what it means that remove duplicates without > >> hampering the array! The hash table anyway would contain all the > >> distinct elements. > >> > >> 2. Pass the array checking if the current element is lower than the > >> previous one. If found such element The current element is the start > >> of the original sorted array. If such element is not found then the > >> first element of the present is the desired element. Note down the > >> index. Takes O(n). > >> > >> Now do binary search. The mid point of the array is manipulated by > >> considering the index that we have saved. One trivial method could be > >> keep track of the array in each recursion and then get the half length > >> and then calculate the index according to the placement of the > >> starting index at that recursion. This takes O(logn). > >> > >> So overall Time O(n). Space O(1) [no extra space]. > >> > >> > >> Correct me if I am wrong. > >> > >> -Abhirup > >> > >> > >> > >> > >> On Fri, Jul 2, 2010 at 1:50 AM, Vikas Jayaprakash > >> <[email protected]> wrote: > >> > Hi AlgoGeeks, > >> > Can anyone provide me answers for the below. > >> > > >> > 1. given an array of random integers write a program to (1) detect > >> > duplicate (2) remove duplicate (array should not get hampered at any > >> > cost!). > >> > 2 - In a sorted array some of the elements say N are rotated. for > >> > example initially 1 2 3 6 7 8 9 after rotation of 3 elements 7 8 9 1 2 > >> > 3 6.So how do you search an element in this array? > >> > > >> > > >> > Regards, > >> > Vikas J > >> > > >> > -- > >> > 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]<algogeeks%[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]<algogeeks%[email protected]> > . > >> For more options, visit this group at > >> http://groups.google.com/group/algogeeks?hl=en. > >> > > > > > > > > -- > > With Regards, > > Jalaj Jaiswal > > +919026283397 > > B.TECH IT > > IIIT ALLAHABAD > > > > -- > > 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]<algogeeks%[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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Thanks & Regards, Vikas Jayaprakash -- 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.
