Millet Porridge

English version of https://corvo.myseu.cn

0%

Another Variant of Finding the Non-Repeating Number in a Sequence

Posted on Edited on In Disqus:
I once met the problem where one number appears once in an array and all others appear twice, asking for that single number — solved with XOR in O(1) space and O(n) time. Today while browsing other blogs I happened upon another variant; sharing the solution strategy here.

The original post is here: Thoughts inspired by a Tencent algorithm problem. Since there was no place to leave him a comment about this solution, I’ll just dash off a blog post.

The Problem

The problem is roughly:

There are currently ten thousand and one numbers (unordered), in the range 1~10000. Except for two duplicated numbers, all other numbers are unique. How to find these two duplicate numbers fastest?

A simple analysis: 1~10000 is 10000 numbers in total, so the one extra number is the duplicated number we’re looking for.

Take the array below as an example; the final 23 is what we want.

1
[1, 2, 3, 4, ..., 10000, 23]

Of course the example above is simple — the answer is visible at a glance; a shuffled array is not so easy to see through.

How to Solve It

A shuffled array is indeed hard to judge, so let’s still look at this special ordered form.

Please try marking the array indices, into a table like this:
array value 1 2 3 4 5 ….. 10000 23
array index 0 1 2 3 4 …. 9999 10000

Have you noticed — merging the array indices with the original array values, what does it look like?

1
0, 1, 1, 2, 2, 3, 3, 4, 4 ...  10000, 10000, 23

The problem then transforms into: in 1~10000, all numbers appear twice (excluding 0), one number appears three times, and we need to find this number — just bring out our XOR method.

The array above is in order; even a shuffled array can always be rearranged to obtain this relationship.

Below is my solution, written directly in Python for convenience:

1
2
3
4
5
6
7
8
9
10
11
import random
x = list(range(1, 10001))  # array of 1 ~ 10000
x.append(238)  # arbitrarily given target number
random.shuffle(x)  # shuffle the whole array

rlt = 0
for idx, num in enumerate(x):
    rlt = rlt ^ idx ^ num  # continuous XOR over array elements and indices

print(rlt)
# will definitely get 238

Time and Space Complexity Analysis

Since the problem specifies 10001 numbers, the time complexity works out to O(10000), and the space complexity is O(1).

Not being able to leave a comment is really annoying — I hope everyone’s blogs can add a message board too, for the sake of communication.

Related Posts