Finding an element in an array where every element is repeated odd number of times and only one appears once?

I believe you can still use the basic idea of XOR to solve this problem in a clever fashion.

I believe you can still use the basic idea of XOR to solve this problem in a clever fashion. First, let's change the problem so that one number appears once and all other numbers appear three times. Algorithm: Here A is the array of length n: int ones = 0; int twos = 0; int not_threes, x; for (int i=0; iThis uses O(n) time and O(1) space.

I believe I can extend this idea to the general case of the problem, but possibly one of you can do it faster, so I'll leave this for now and edit it when and if I can generalize the solution. Explanation: If the problem were this: "one element appears once, all others an even number of times", then the solution would be to XOR the elements. The reason is that x^x = 0, so all the paired elements would vanish leaving only the lonely element.

If we tried the same tactic here, we would be left with the XOR of distinct elements, which is not what we want. Instead, the algorithm above does the following: ones is the XOR of all elements that have appeared exactly once so far twos is the XOR of all elements that have appeared exactly twice so far Each time we take x to be the next element in the array, there are three cases: if this is the first time x has appeared, it is XORed into ones if this is the second time x has appeared, it is taken out of ones (by XORing it again) and XORed into twos if this is the third time x has appeared, it is taken out of ones and twos. Therefore, in the end, ones will be the XOR of just one element, the lonely element that is not repeated.

There are 5 lines of code that we need to look at to see why this works: the five after x = Ai. If this is the first time x has appeared, then ones&x=ones so twos remains unchanged. The line ones ^= x; XORs x with ones as claimed.

Therefore x is in exactly one of ones and twos, so nothing happens in the last three lines to either ones or twos. If this is the second time x has appeared, then ones already has x (by the explanation above), so now twos gets it with the line twos |= ones & x;. Also, since ones has x, the line ones ^= x; removes x from ones (because x^x=0).

Once again, the last three lines do nothing since exactly one of ones and twos now has x. If this is the third time x has appeared, then ones does not have x but twos does. So the first line let's twos keep x and the second adds x to ones.

Now, since both ones and twos have x, the last three lines remove x from both. Generalization: If some numbers appear 5 times, then this algorithm still works. This is because the 4th time x appears, it is in neither ones nor twos.

The first two lines then add x to ones and not twos and the last three lines do nothing. The 5th time x appears, it is in ones but not twos. The first line adds it to twos, the second removed it from ones, and the last three lines do nothing.

The problem is that the 6th time x appears, it is taken from ones and twos, so it gets added back to ones on the 7th pass. I'm trying to think of a clever way to prevent this, but so far I'm coming up empty.

Doesn't op's solution have the same complexity. – Luchian Grigore Sep 7 '11 at 18:13 @Luchian: Same time, not same space. In any event, at least I'm using the oddness of the problem :-) – PengOne Sep 7 '11 at 18:14 1 I like your solution so far; for generalizing it consider NOT removing x from from ones and twos.

Then, at the end of your function, ones holds values that have appeared 1 or more times, while twos holds values that have appeared 2 or more times. XOR them together and viola. I'll admit, I'm not certain this works.

– Bob2Chiv Sep 7 '11 at 20:01 1 @IVlad: Are you certain you've implemented it correctly? My implementation (in C) produces the output 2 for the input {1,2,1,1}. – PengOne Sep 7 '11 at 20:12 1 It's not possible to generalize this solution.

See my answer for both an explanation of why and a clearer explanation of what the code in this answer is doing. – Keith Irwin Sep 7 '117 at 21:59.

For the problem as stated it is most likely that the most efficient answer is the O(n) space answer. On the other hand, if we narrow the problem to be "All numbers appear n times except for one which only appears once" or even "All numbers appear a multiple of n times except for one which only appears once" then there's a fairly straightforward solution for any n (greater than 1, obviously) which takes only O(1) space, which is to break each number into bits and then count how many times each bit is turned on and take that modulo n. If the result is 1, then it should be turned on in the answer.

If it is 0, then it should be turned off. (Any other answer shows that the parameters of the problem did not hold). If we examine the situation where n is 2, we can see that using XOR does exactly this (bitwise addition modulo 2).

We're just generalizing things to do bitwise addition modulo n for other values of n. This, by the way, is what the other answer for n=3 does, it's actually just a complex way of doing bit-wise addition where it stores a 2-bit count for each bit. The int called "ones" contains the ones bit of the count and the int called "twos" contains the twos bit of the count.

The int not_threes is used to set both bits back to zero when the count reaches 3, thus counting the bits modulo 3 rather than normally (which would be modulo 4 since the bits would wrap around). The easiest way to understand his code is as a 2-bit accumulator with an extra part to make it work modulo 3. So, for the case of all numbers appearing a multiple of 3 times except the one unique number, we can write the following code for 32 bit integers: int findUnique(int A, int size) { // First we set up a bit vector and initialize it to 0.Int count32; for (int j=0;j>= 1; } } // Then we just have to reassemble the answer by putting together any // bits which didn't appear a multiple of 3 times.

Int answer = 0; for (int j=0;jBut I haven't bothered to do that since it has no effect on the asymptotic complexity. If we wish to change the parameters of the problem so that instead the numbers are repeated 5 times, we just change the 3s to 5s. Or we can do likewise for 7, 11, 137, 727, or any other number (including even numbers).

But instead of using the actual number, we can use any factor of it, so for 9, we could just leave it as 3, and for even numbers we can just use 2 (and hence just use xor). However, there is no general bit-counting based solution for the original problem where a number can be repeated any odd number of times. This is because even if we count the bits exactly without using modulo, when we look at a particular bit, we simply can't know whether the 9 times it appears represents 3 + 3 + 3 or 1 + 3 + 5.

If it was turned on in three different numbers which each appeared three times, then it should be turned off in our answer. If it was turned on in a number which appeared once, a number which appeared three times, and a number which appeared five times, then it should be turned on in our answer. But with just the count of the bits, it's impossible for us to know this.

This is why the other answer doesn't generalize and the clever idea to handle the special cases is not going to materialize: any scheme based on looking at things bit by bit to figure out which bits should be turned on or off does not generalize. Given this, I don't think that any scheme which takes space O(1) works for the general case. It is possible that there are clever schemes which use O(lg n) space or so forth, but I would doubt it.

I think that the O(n) space approach is probably the best which can be done in the problem as proposed. I can't prove it, but at this point, it's what my gut tells me and I hope that I've at least convinced you that small tweaks to the "even number" technique are not going to cut it.

I know that the subtext of this question is to find an efficient or performant solution, but I think that the simplest, readable code counts for a lot and in most cases it is more than sufficient. So how about this: var value = (new { 1, 6, 3, 1, 1, 6, 6, 9, 3, 3, 3, 3, }) . ToLookup(x => x) .

Where(xs => xs.Count() == 1) .First() . Key; Good old LINQ. :-).

No, I think the specified approach is the best you can do in this case. Little to no efficiency can be gained from the fact that they repeat an odd number of times for this purpose.

– PengOne Sep 7 '11 at 17:41 My reasoning is that since you need to count the data in some manner, being an odd/even count (or any count more than one) doesn't matter. The only small efficiency that can be gained from the 'odd' count requirement is: In some cases you may not have to read the last character if you have one with count 1. In large lists, this makes no difference; but in small lists or with great I/O time it could be important.

– Bob2Chiv Sep 7 '11 at 17:55 Not necessarily. Many problems such as this have tricky solutions that avoid counting multiplicities (e.g. If exactly one number is repeated). – PengOne Sep 7 '11 at 17:57 Yes, but I don't think this is one of those problems :) – Tom Zych Sep 7 '11 at 18:05 I agree, but I don't think this is a case.

I'd be excited to hear of such a solution. – Bob2Chiv Sep 7 '11 at 18:17.

The only way to do it is to count how many times each number appears. You don't have to keep counting once a given number's count exceeds 2, but you do have to count them.

– PengOne Sep 7 '11 at 17:42 @PengOne: We want to find the number that appears only once. There is no way to tell if it appears only once except to count how many times it appears. And without knowing the answer in advance, we can't tell which one it is until we've looked at all the data and counted all the numbers.

– Tom Zych Sep 7 '11 at 17:47 1 I don't see why your second sentence is true. I also do not see a slick answer to this question, but that doesn't mean that one does not exist. If the "odd" part of the question is unnecessary, then why was it phrased that way?

Without an argument as to why the problem is the same without that condition, I'm not so willing to dismiss the information as useless. – PengOne Sep 7 '11 at 17:49 I believe you're saying you have to check all the numbers, not count them. In which case, I agree.

– Luchian Grigore Sep 7 '11 at 17:51 Well, instead of counting them, I suppose you could maintain two sets: those that have been seen once, and those that have been seen more than once. I suppose that's technically distinct from counting. – Tom Zych Sep 7 '11 at 17:55.

I would use some loops to pick a number, work through the list until it repeats once, then break out and check the next number. Repeat this until you find one that doesn't repeat. No need to see if it repeats 3 times since once it repeats, it's not what your looking for.

Needlessly inefficient. – Tom Zych Sep 7 '11 at 17:41 how is this better than what he suggested? – Luchian Grigore Sep 7 '11 at 17:42.

I would do this in two loops. Once loop to get the distinct numbers and another to track which numbers are not duplicated in the way you want. A as array; be as array; loop(eg as i){ if (i not in a) { a.

Insert(i); } ba. Indexof(i) = ba. Indexof(i) + 1; } loop(b as i) { if I one of these (1,...){ echo i; } }.

This is worse than what op suggested. – Luchian Grigore Sep 7 '11 at 17:45.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.