Member Avatar for techie1991

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
  • 104 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by youwill
Member Avatar for Momerath

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 because: n/a
commented: good answer.. +2
commented: Good use of XOR +4
Member Avatar for techie1991

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

Member Avatar for youwill

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.