The lonely loner

Computer Science Level 4

Every integer in this random array of integers is repeated except for one. This single number does not have a duplicate. Who is the loner?

The answer is 2016.

3 solutions

Thaddeus Abiy
Jul 25, 2016

Behold the power of XOR!

1	`print reduce(lambda x,y:x^y,array) # MAGIC!`

where the variable array is the array of numbers. .

Explanation

Notice that the $XOR$ operation is commutative $a \ XOR \ b = b \ XOR \ a$ and associative $a \ XOR \ (b \ XOR \ c) = \ c \ XOR \ (a \ XOR \ B)$ Also notice that the 0 is the identity value for the $XOR$ operation $a \ XOR \ 0 \ = \ a$ This means we can just $XOR$ every value and obtain the answer because all the pairs will reduce to $0$ , except for the loner .

neat solution!!

Beakal Tiliksew - 4 years, 10 months ago

Brilliant !

You Kad - 4 years, 10 months ago

This only works when there is an even quantity of each repeating number, right? If there are three repetitions of a number, your code will produce the wrong result. It's also not clear in the question that all numbers but one come in pairs.

Lucas Viana Reis - 3 years ago

Rushikesh Jogdand
Jul 27, 2016

data=[29105, 9929, 24497, 27350, 3045, 9323, 4083, 11194, 4383, 29417, 7230, 3245, 6393, 2478, 3170, 958, 20243, 10713, 5446, 19871, ...]
for i in list(set(data))):
    if data.count(i)==1:
        print(i)
        break

This takes quadratic time, which is very slow. I believe it takes a very long time (at least an hour); how did you manage to be patient enough to wait for it? Or rather, how long did it take?

Ivan Koswara - 4 years, 10 months ago

I haven't thought of time complexity of this program, but it executed under 1 minute.

Rushikesh Jogdand - 4 years, 10 months ago

The XOR method given by the setter is very neat solution, runs in O(n) time and does not require knowledge of the size of the greatest value, and it's single pass, and can operate on the data directly and take O(1) storage.

A naive algorithm would be a simple three pass one which has O(value-range) time and O(value-range) space. Pass 1: find range values and allocate and zero out bit vector of length value-range. Pass 2: Set vector[value-minRange] = 1 xor vector[value-minRange]; Pass 3: Scan vector to find the first bit <> 0.

A two pass algorithm. Could use a hash table and keep a count of the number of time a value has been seen. Then scan the table to find which key has a count-value of 1. Looks like O(n) time and O(n) space. (A hash table can iterate over all entries but not in a controlled order).

It is hard to know the computation complexity of a given library or language's built-in algorithm and it may well be that set(data) is O(n^2) or worse.

Ed Sirett - 4 years, 8 months ago

You Kad
Jul 28, 2016

1 2	`from collections import Counter print(Counter(array).most_common()[-1]) # "array" is the array of numbers`

Another way of doing this is by first sorting the array. Then scan for n and n+1 term to be equal, else break, and at the end of loop n=n+2.

Akira Kato - 4 years, 10 months ago

Sorting the array takes $O(n \lg n)$ time. Assuming a perfect hash table (used for Counter ), it takes only $O(n)$ time.

Ivan Koswara - 4 years, 10 months ago

The lonely loner

The answer is 2016.

3 solutions

0 pending reports