0

I was looking at a question:
Q. Given n numbers of which all numbers are repeated (at least once) other than one. We have to find that number.

Numbers range is to 10^9, thus using count sort would do no good.!

Adding the numbers one by one to a dictionary was another option (and a good one as the complexity is O(n)). But this has high implementation requirements.!

Can someone suggest some better answer to this problem.? :-/

4
Contributors
4
Replies
5
Views
6 Years
Discussion Span
Last Post by youwill
2

O(n) solution:

int value;
for(int i = 0; i < myArray.Length; i++) {
    value ^= myArray[i];
}

Console.WriteLine("{0} occurs only once", value);

Works when all other numbers come in pairs. Make sure I get a good grade.

Edited by Momerath: n/a

Votes + Comments
Good use of XOR
good answer..
0

very good answer momerath..
I must really start using these boolean operators.. :)

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.