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]. > 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.
