0
$\begingroup$

I am given a sorted array with n integers. All of the elements repeat exactly twice, while there is one element without duplicate. I need to solve it as efficient as it is possible by divide-and-conquer algorithm. I have noticed that n needs to be odd to satisfy my condition. I thought about doing this: divide my array in two parts from the mid, if from [0, mid] or [mid, end] I have odd number of elements then my elements is in that half. So, recursively divide also that subarray and so on.

  1. How to decide which part of the array to look at first?
  2. Does this solution take O(logn)?
  3. Is there other effective approach?
$\endgroup$
5
  • 1
    $\begingroup$ Since the array is sorted, why not simply walk through it and look for the unrepeated element? That'll take $O(n)$ time and you can't do better than that. $\endgroup$ Feb 21 at 18:23
  • $\begingroup$ Actually, this approach is indeed in $O(\log(n))$. $\endgroup$
    – Hugo Manet
    Feb 21 at 18:25
  • $\begingroup$ @HugoManet why? Can you elaborate? $\endgroup$
    – Diana
    Feb 21 at 18:30
  • $\begingroup$ @RickDecker I need to use divide and conquer approach. $\endgroup$
    – Diana
    Feb 21 at 18:31
  • $\begingroup$ @HugoManet thank you very much for the answer. Tbh, I don't quite get that part "to decide where 𝑢 is, you can take a random position in the array, and just have to ask whether you're in the first part (where doubles start on even indexes) or the second part (where doubles start on odd indexes)." Could you, please, explain it in pseudocode? $\endgroup$
    – Diana
    Feb 21 at 19:08
0
$\begingroup$

Assume elements start at index 0. N is odd.

Let mid be an even number close to the middle of the array. Compare a[mid-1] and a[mid]. There is an odd number of elements before mid-1 and an even number after mid.

If both numbers are equal then the unique one is in the left half < mid-1. If they are not equal then the unique one is in the right half starting at mid.

$\endgroup$
1
$\begingroup$

This is a classical problem when the array isn't sorted, which has a surprising, almost magical linear solution.

But here, with a sorted array, your idea is great.

The unique element will have an index $u$, and every element $a[i]$ will be exactly the same as either $a[i-1]$ or $a[i+1]$ (which are different). Assuming that arrays start at $0$, the shape of the (sorted) array is first a list of elements where $a[2i] = a[2i+1]$, then $a[u]$, then a list of elements where $a[2i-1] = a[2i]$.

So to decide where $u$ is, you can take a random position in the array, and just have to ask whether you're in the first part (where doubles start on even indexes) or the second part (where doubles start on odd indexes). This takes a constant number of operation by question, and each question reduces the size of the search array by $2$ (if you sample in the middle, of course).

So, to synthesize :

  1. By looking in the middle, you ensure that the next part you have to look at will be as small as possible
  2. This yields a $\log(n)$ algorithm
  3. This approach is probably optimal, but the proof that there isn't something better to do must be quite hard, so I leave it to someone else ^^
$\endgroup$
1
  • 1
    $\begingroup$ It is worst-case optimal by a simple information-theoretic argument: there are $\Theta(n)$ possible outcomes. To be able to encode every possible outcomes, you need $\Omega(\log n)$ bits of information, and thus $\Omega(\log n)$ operations. $\endgroup$
    – Tassle
    Feb 21 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.