Alex Rivera | Logout

How can I find a number which occurs an odd number of times in a SORTED array in O(n) time?

Asked 2010-07-05T16:50:00.657
40

I have a question and I tried to think over it again and again... but got nothing so posting the question here. Maybe I could get some view-point of others, to try and make it work...

The question is: we are given a SORTED array, which consists of a collection of values occurring an EVEN number of times, except one, which occurs ODD number of times. We need to find the solution in log n time.

It is easy to find the solution in O(n) time, but it looks pretty tricky to perform in log n time.

c algorithm asymptotic-complexity
Edit
Report

1 Answer

0

The clue is you're looking for log(n). That's less than n.

Stepping through the entire array, one at a time? That's n. That's not going to work.

We know the first two indexes in the array (0 and 1) should be the same number. Same with 50 and 51, if the odd number in the array is after them.

So find the middle element in the array, compare it to the element right after it. If the change in numbers happens on the wrong index, we know the odd number in the array is before it; otherwise, it's after. With one set of comparisons, we figure out which half of the array the target is in.

Keep going from there.

answered 2010-07-12T17:20:00.647

Your Answer