# Find a number with even number of occurrences

Given an array where number of occurrences of each number is odd except one number whose number of occurrences is even. Find the number with even occurrences.

e.g.

``````1, 1, 2, 3, 1, 2, 5, 3, 3
``````

Output should be:

``````2
``````

The below are the constraints:

1. Numbers are not in range.
2. Do it in-place.
3. Required time complexity is O(N).
4. Array may contain negative numbers.
5. Array is not sorted.

With the above constraints, all my thoughts failed: comparison based sorting, counting sort, BST's, hashing, brute-force.

I am curious to know: Will XORing work here? If yes, how?

-
No, it won't. Look at the counter example: `[1,1,1,5,2,2]`. 1 XOR 1 XOR 1 XOR 5 XOR 2 XOR 2 == 001 ^ 001 ^ 001 ^101 ^ 010 ^ 010 == 100 –  amit Sep 9 '12 at 20:41
Not sure about the complexity, but can't you have two hash-sets, one in which you store all seen numbers, and one in which you store a number first time you see it, remove it the second time you see it and so on. In the end you would have one set (A) with all numbers, and one set (B) with all odd-occuring numbers. You should then be able to subtract (B) from (A) in linear time, which should yield the result. (This assumes a suitable hash function though. )-: –  aioobe Sep 9 '12 at 20:44
@aioobe: I believe by "in place" the OP is looking for `O(1)` space solution. (Otherwise a simple histogram and then iterating it will do) –  amit Sep 9 '12 at 20:45
@Aashish: do you have reason to believe that a solution exists, if so what reason? In the case where someone provides an input in which all values occur once except for one that occurs twice, solving this problem is like finding a duplicate. Depending on your computation model and what you mean by "numbers are not in range", finding a duplicate in `O(N)` time might be impossible. –  Steve Jessop Sep 9 '12 at 20:50
Do you know something about the input values? What does "not in range" mean? Would a solution with sorage in O(m) where m is the number of different values would be satisfactory? –  alestanis Oct 21 '12 at 17:40

Introduction

Here is a possible solution. It is rather contrived and not practical, but then, so is the problem. I would appreciate any comments if I have holes in my analysis. If this was a homework or challenge problem with an “official” solution, I’d also love to see that if the original poster is still about, given that more than a month has passed since it was asked.

First, we need to flesh out a few ill-specified details of the problem. Time complexity required is `O(N)`, but what is `N`? Most commentators appear to be assuming `N` is the number of elements in the array. This would be okay if the numbers in the array were of fixed maximum size, in which case Michael G’s solution of radix sort would solve the problem. But, I interpret constraint #1, in absence of clarification by the original poster, as saying the maximum number of digits need not be fixed. Therefore, if `n` (lowercase) is the number of elements in the array, and `m` the average length of the elements, then the total input size to contend with is `mn`. A lower bound on the solution time is `O(mn)` because this is the read-through time of the input needed to verify a solution. So, we want a solution that is linear with respect to total input size `N = nm`.

For example, we might have `n = m`, that is `sqrt(N)` elements of `sqrt(N)` average length. A comparison sort would take `O( log(N) sqrt(N) ) < O(N)` operations, but this is not a victory, because the operations themselves on average take `O(m) = O(sqrt(N))` time, so we are back to `O( N log(N) )`.

Also, a radix sort would take `O(mn) = O(N)` if `m` were the maximum length instead of average length. The maximum and average length would be on the same order if the numbers were assumed to fall in some bounded range, but if not we might have a small percentage with a large and variable number of digits and a large percentage with a small number of digits. For example, 10% of the numbers could be of length `m^1.1` and 90% of length `m*(1-10%*m^0.1)/90%`. The average length would be `m`, but the maximum length `m^1.1`, so the radix sort would be `O(m^1.1 n) > O(N)`.

Lest there be any concern that I have changed the problem definition too dramatically, my goal is still to describe an algorithm with time complexity linear to the number of elements, that is `O(n)`. But, I will also need to perform operations of linear time complexity on the length of each element, so that on average over all the elements these operations will be `O(m)`. Those operations will be multiplication and addition needed to compute hash functions on the elements and comparison. And if indeed this solution solves the problem in `O(N) = O(nm)`, this should be optimal complexity as it takes the same time to verify an answer.

One other detail omitted from the problem definition is whether we are allowed to destroy the data as we process it. I am going to do so for the sake of simplicity, but I think with extra care it could be avoided.

Possible Solution

First, the constraint that there may be negative numbers is an empty one. With one pass through the data, we will record the minimum element, `z`, and the number of elements, `n`. On a second pass, we will add `(3-z)` to each element, so the smallest element is now 3. (Note that a constant number of numbers might overflow as a result, so we should do a constant number of additional passes through the data first to test these for solutions.) Once we have our solution, we simply subtract `(3-z)` to return it to its original form. Now we have available three special marker values `0`, `1`, and `2`, which are not themselves elements.

Step 1

Use the median-of-medians selection algorithm to determine the 90th percentile element, `p`, of the array `A` and partition the array into set two sets `S` and `T` where `S` has the `10% of n` elements greater than `p` and `T` has the elements less than `p`. This takes `O(n)` steps (with steps taking `O(m)` on average for `O(N)` total) time. Elements matching `p` could be placed either into `S` or `T`, but for the sake of simplicity, run through array once and test `p` and eliminate it by replacing it with `0`. Set `S` originally spans indexes `0..s`, where `s` is about `10%` of `n`, and set `T` spans the remaining 90% of indexes `s+1..n`.

Step 2

Now we are going to loop through `i in 0..s` and for each element `e_i` we are going to compute a hash function `h(e_i)` into `s+1..n`. We’ll use universal hashing to get uniform distribution. So, our hashing function will do multiplication and addition and take linear time on each element with respect to its length.

We’ll use a modified linear probing strategy for collisions:

1. `h(e_i)` is occupied by a member of `T` (meaning `A[ h(e_i) ] < p` but is not a marker `1` or `2`) or is `0`. This is a hash table miss. Insert `e_i` by swapping elements from slots `i` and `h(e_i)`.

2. `h(e_i)` is occupied by a member of `S` (meaning `A[ h(e_i) ] > p`) or markers `1` or `2`. This is a hash table collision. Do linear probing until either encountering a duplicate of `e_i` or a member of `T` or `0`.

• If a member of `T`, this is a again a hash table miss, so insert `e_i` as in `(1.)` by swapping to slot `i`.

• If a duplicate of `e_i`, this is a hash table hit. Examine the next element. If that element is `1` or `2`, we’ve seen `e_i` more than once already, change `1`s into `2`s and vice versa to track its change in parity. If the next element is not `1` or `2`, then we’ve only seen `e_i` once before. We want to store a `2` into the next element to indicate we’ve now seen `e_i` an even number of times. We look for the next “empty” slot, that is one occupied by a member of `T` which we’ll move to slot `i`, or a 0, and shift the elements back up to index `h(e_i)+1` down so we have room next to `h(e_i)` to store our parity information. Note we do not need to store `e_i` itself again, so we’ve used up no extra space.

So basically we have a functional hash table with 9-fold the number of slots as elements we wish to hash. Once we start getting hits, we begin storing parity information as well, so we may end up with only 4.5-fold number of slots, still a very low load factor. There are several collision strategies that could work here, but since our load factor is low, the average number of collisions should be also be low and linear probing should resolve them with suitable time complexity on average.

Step 3

Once we finished hashing elements of `0..s` into `s+1..n`, we traverse `s+1..n`. If we find an element of S followed by a `2`, that is our goal element and we are done. Any element `e` of `S` followed by another element of `S` indicates `e` was encountered only once and can be zeroed out. Likewise `e` followed by a `1` means we saw `e` an odd number of times, and we can zero out the `e` and the marker `1`.

Rinse and Repeat as Desired

If we have not found our goal element, we repeat the process. Our 90th percentile partition will move the 10% of `n` remaining largest elements to the beginning of `A` and the remaining elements, including the empty `0`-marker slots to the end. We continue as before with the hashing. We have to do this at most 10 times as we process 10% of `n` each time.

Concluding Analysis

Partitioning via the median-of-medians algorithm has time complexity of `O(N)`, which we do 10 times, still `O(N)`. Each hash operation takes `O(1)` on average since the hash table load is low and there are `O(n)` hash operations in total performed (about 10% of n for each of the 10 repetitions). Each of the `n` elements have a hash function computed for them, with time complexity linear to their length, so on average over all the elements `O(m)`. Thus, the hashing operations in aggregate are `O(mn) = O(N)`. So, if I have analyzed this properly, then on whole this algorithm is `O(N)+O(N)=O(N)`. (It is also `O(n)` if operations of addition, multiplication, comparison, and swapping are assumed to be constant time with respect to input.)

Note that this algorithm does not utilize the special nature of the problem definition that only one element has an even number of occurrences. That we did not utilize this special nature of the problem definition leaves open the possibility that a better (more clever) algorithm exists, but it would ultimately also have to be O(N).

-

This problem has been occupying my subway rides for several days. Here are my thoughts.

If A. Webb is right and this problem comes from an interview or is some sort of academic problem, we should think about the (wrong) assumptions we are making, and maybe try to explore some simple cases.

The two extreme subproblems that come to mind are the following:

• The array contains two values: one of them is repeated an even number of times, and the other is repeated an odd number of times.
• The array contains n-1 different values: all values are present once, except one value that is present twice.

Maybe we should split cases by complexity of number of different values.

If we suppose that the number of different values is O(1), each array would have `m` different values, with `m` independent from `n`. In this case, we could loop through the original array erasing and counting occurrences of each value. In the example it would give

``````1, 1, 2, 3, 1, 2, 5, 3, 3 -> First value is 1 so count and erase all 1
2, 3, 2, 5, 3, 3 -> Second value is 2, count and erase
-> Stop because 2 was found an even number of times.
``````

This would solve the first extreme example with a complexity of `O(mn)`, which evaluates to `O(n)`.

There's better: if the number of different values is `O(1)`, we could count value appearances inside a hash map, go through them after reading the whole array and return the one that appears an even number of times. This woud still be considered `O(1)` memory.

The second extreme case would consist in finding the only repeated value inside an array. This seems impossible in `O(n)`, but there are special cases where we can: if the array has `n` elements and values inside are `{1, n-1}` + repeated value (or some variant like all numbers between x and y). In this case, we sum all the values, substract `n(n-1)/2` from the sum, and retrieve the repeated value.

Solving the second extreme case with random values inside the array, or the general case where `m` is not constant on `n`, in constant memory and `O(n)` time seems impossible to me.

Extra note: here, XORing doesn't work because the number we want appears an even number of times and others appear an odd number of times. If the problem was "give the number that appears an odd number of times, all other numbers appear an even number of times" we could XOR all the values and find the odd one at the end.

We could try to look for a method using this logic: we would need something like a function, that applied an odd number of times on a number would yield 0, and an even number of times would be identity. Don't think this is possible.

-
If it is an academic or interview question, this is how you should attempt to answer - talk it out and explain your thought process. I wouldn't jump to the "impossible" in an interview situation though, but conclude with "I'd like to think more about this when I have more time" instead. –  A. Webb Oct 25 '12 at 18:41
That is, unless you prove it impossible. The bit, "...a function, that applied an odd number of times on a number would yield 0, and an even number of times would be identity. Don't think this is possible." is indeed provably not possible. If f(x) = 0. Then f(f(x)) = f(0), a constant, for any input x. This, of course, is not the only way to attack the problem. –  A. Webb Oct 25 '12 at 18:47
@A.Webb I wouldn't have said impossible either in an interview. But I would have presented all the cases I could solve, even the very specific on where numbers are in [1, n-1] and each number appears once. –  alestanis Oct 25 '12 at 19:03
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}