Find the unduplicated element in a sorted array

Question

Source : Microsoft Interview Question

Given a sorted array, in which every element is present twice except one which is present single time, we need to find that element.

Now a standard O(n) solution is to do a XOR of list, which will return the unduplicated element (since all duplicated elements cancel out.)

Is it possible to solve this more quickly if we know the array is sorted?

Do a binary "search" (rather traversal) on the array, check both neighbors, if bot are different from the middle value, you have the solution. This is `O(log n)`. — , Jun 14 '13 at 21:18
@ZiyaoWei Nopeeeee! I just don't speak English. If the array is sorted, (`1 1 2 2 3 4 4`), then one neighbor is the same as the central value. — , Jun 14 '13 at 21:21
@H2CO3 Are you assuming that all the elements are consecutive? If not, how do you decide whether to check the low half or the high half? — jerry, Jun 14 '13 at 21:22
@H2CO3 I was asking if you were assuming that there were no skipped numbers (as in your example). Based on Daniel Fiscer's answer, I understand what you were thinking. I blame my illness :) — jerry, Jun 14 '13 at 21:37
@jerry No, I wasn't - the "am I present twice in the array" aspect has little to nothing to do with the distance of consecutive elements :) The thing is that if the array is sorted, then equal elements are always neighbors - and my approach (ab)uses that fact ;) — , Jun 14 '13 at 21:54

score 15 · Accepted Answer · answered Jun 14 '13 at 21:21

15

Yes, you can use the sortedness to reduce the complexity to O(log n) by doing a binary search.

Since the array is sorted, before the missing element, each value occupies the spots 2*k and 2*k+1 in the array (assuming 0-based indexing).

So you go to the middle of the array, say index h, and check either index h+1 if h is even, or h-1 if h is odd. If the missing element comes later, the values at these positions are equal, if it comes before, the values are different. Repeat until the missing element is located.

answered Jun 14 '13 at 21:21

Daniel Fischer

181,706
17
308
431

3

That's brilliant. Great answer! – templatetypedef Jun 14 '13 at 21:22
1

And now you're getting upvoted for the answer I posted in my comment 3 minutes ago. Sill me :) – Jun 14 '13 at 21:23
1

@H2CO3 I was typing the answer while you were commenting, great minds think alike, don't they? But you're getting upvotes too, deservedly. – Daniel Fischer Jun 14 '13 at 21:24
You're implicitly assuming the elements are consecutive. I'm not sure that's warranted based on the problem description. – jerry Jun 14 '13 at 21:25
@jerry No he is not, but this is just devilishly brilliant:) – zw324 Jun 14 '13 at 21:26
1

@jerry No. All that matters is that the elements are sorted (doesn't even really matter, all we need is that the duplicated elements are next to each other). – Daniel Fischer Jun 14 '13 at 21:26
@Ziyao sure he is: `each value occupies the spots 2*k and 2*k+1`. This is not true for, say, `{1,1,5,5,7,10,10}`. – jerry Jun 14 '13 at 21:27
@jerry Sure, `5` occupies 2 and 3, `1` occupies 0 and 1. – Daniel Fischer Jun 14 '13 at 21:28
@jerry please note that `k` is not the value, it is just as saying even numbers are `2k`. – zw324 Jun 14 '13 at 21:29
I stand corrected, I misunderstood `k` to be the value in question. I clearly didn't read the last paragraph closely enough. Have a +1 :) – jerry Jun 14 '13 at 21:32
@H2CO3 Now the question is, did you reciprocate, or did I? – Daniel Fischer Jun 14 '13 at 21:53
@DanielFischer Well, that's a good question. If you upvoted as well, then we can just agree that we were equally kind to each other ;) – Jun 14 '13 at 21:54
1

@H2CO3 Not for the first time, I believe, nor for the last ;) – Daniel Fischer Jun 14 '13 at 21:55
seems like my question,has bought brotherhood :P – Spandan Jun 14 '13 at 22:06

score 6 · Answer 2 · 2014-02-03T13:50:13.537

6

Do a binary "search" (rather traversal) on the array, check both neighbors, if both are different from the value in the middle, you have the solution. This is O(log n).

edited Feb 03 '14 at 13:50

answered Jun 14 '13 at 21:22

1

you didnt understand d question,i think ! – Spandan Jun 14 '13 at 21:27
2

@Spandan I understood it perfectly. – Jun 14 '13 at 21:52

Siddharth Kumar · Answer 3 · 2019-03-29T06:15:33.637

Yes, The array is sorted so we can apply binary search to find the single element. Let's see the pattern of occurrence of single element. Total number of elements will be always odd and single element occurs only at even index

Total number of elements 9, single elements always present at even index. When (end_index - start_index) % 4 == 0, The single element is occurring in middle.

if A[mid-1] == A[mid] --> single element left side
if A[mid] == A[mid+1] --> single element right side

Total number of elements 11, single elements always present at even index. When (end_index - start_index) % 4 != 0, The single element is not occurring in middle.

if A[mid] == A[mid+1] --> single element left
if A[mid-1] == A[mid] --> single element right

Total number of elements 13, single elements always present at even index. When (end_index - start_index) % 4 == 0, The single element is occurring at middle also.

if A[mid-1] == A[mid] --> single element left side
if A[mid] == A[mid+1] --> single element right side

Below is the Python Code:

class Solution:
    def singleNonDuplicate(self, A):
        """
        :type nums: List[int]
        :rtype: int
        """
        L = len(A)

        def binarySearch(A, start, end):
            if start == end:
                return A[start]

            if start < end:

                mid = int(start + (end - start)/2)

                if A[mid-1] < A[mid] < A[mid+1]:
                    return A[mid]
                if end - start == 2:
                    if A[end] != A[end-1]:
                        return A[end]
                if end - start == 2:
                    if A[start] != A[start+1]:
                        return A[start]
                if A[mid] == A[mid+1]:
                    if int(end-start)%4 == 0:
                        return binarySearch(A, mid+2, end)
                    else:
                        return binarySearch(A, start, mid-1)

                elif A[mid-1] == A[mid]:
                    if int(end - start)%4 == 0:
                        return binarySearch(A, start, mid-2)
                    else:
                        return binarySearch(A, mid+1, end)

        return binarySearch(A, 0, L-1)


if __name__ == "__main__":

    s = Solution()
    A = [1,1,2,3,3,4,4,5,5,6,6]
    r = s.singleNonDuplicate(A)
    print(r)

Find the unduplicated element in a sorted array

3 Answers3

Linked