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 <jalaj.jaiswa...@gmail.com> 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 <abhiru...@gmail.com> 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 >> <vikas.jayaprak...@gmail.com> 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 algoge...@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 algoge...@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. >> > > > > -- > 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 algoge...@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 algoge...@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.
