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.? :-/

Recommended Answers

All 4 Replies

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.

commented: good answer.. +2
commented: Good use of XOR +4

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

absolute this is a good method~~

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.