There is a sorted array which is of very large size. In it every element is repeated more than once except one element. How can I find the unrepeated element in O(log n) time complextiy.
Asked
Active
Viewed 83 times
1
-
Is there a constant number of times that each element (except for that one element) is repeated? – barak manos Feb 03 '14 at 12:27
-
if you knew items are repeated exactly x times you could use indexes.. dosent seem possible this way.. – WeaselFox Feb 03 '14 at 12:28
-
1How can you expect to do it in O(log n) when visiting each element takes at least O(n)? – Morten Zilmer Feb 03 '14 at 12:28
-
Are you allowed to create any additional structures? Because if you don't care about space - you can create something like hash-map and re-use it later as many times as you wish – Alma Do Feb 03 '14 at 12:35
-
@Akash Goyal If each repeating element repeats the same number of times , then it can be done in log(N) time complexity , otherwise we have to do a linear search , see this link http://stackoverflow.com/questions/17117375/find-the-unduplicated-element-in-a-sorted-array – Aseem Goyal Feb 03 '14 at 13:30
1 Answers
1
I say it cant be done. Had the question been something along these lines, where every element repeats exactly twice, than the index of the element could be deduced. I am guessing the OP misunderstood the question.
