Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can anybody help with this? This problem have to be solved using programming language Java or C++. (Or just advice algorithm).

Task: We have $N$ ($N \le 10, 000, 000$) numbers in range from $-1,000,000,000$ to $1 ,000 ,000 ,000$. Most have a duplicate, but two are unique. We have to find the two unique numbers.

Input:
$N$ Numbers, delimited with space char

Output: The two unique numbers

Examples:

Input:

6
4 8 4 7 9 9

Output:

7 8

Input:

8
7 7 5 5 5 5 5 6

Output:

5 6
share|improve this question

closed as unclear what you're asking by Clive Newstead, Matt Pressland, Raskolnikov, Zander, O.L. Jul 4 '13 at 14:37

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
I've voted to close because it's unclear what is being asked here. –  Clive Newstead Jul 4 '13 at 14:15
1  
How's 5 unique in the second example? –  Raskolnikov Jul 4 '13 at 14:24
    
You can find a good solution here: shamasis.net/2009/09/… –  vadim123 Jul 4 '13 at 14:35
    
@vadim123 This is a contest question, not a programming one. There is a nice $O(N)$ solution, but I will not post it here, unless the OP states the context of his question, so that I know it is not cheating. –  dtldarek Jul 4 '13 at 15:45

1 Answer 1

up vote 2 down vote accepted

This question has been answered here, on stackoverflow. In short, the suggested approach there is to use XOR. You can look this up here if you need help on what XOR means. If you don't already know about this forum you should definitely check it out - you can log in with your same credentials as for this site, but that one's for programming questions. Personally, I sometimes struggle as to where I ought to post my computation / numerics questions between these two forums. If you are looking for help coding this algorithm in a specific language, I would recommend searching and then posting in the stackoverflow forums.

share|improve this answer
3  
This algorithm only works if: (1) there is a single unique item, and (2) all other items appear an even number of times. Neither condition applies to OP. –  vadim123 Jul 4 '13 at 14:40
    
Sort the list and then measure the lengths of each consecutive sequence of the same number. The lists with an odd number of entries each correspond to having an element that is unpaired. The time complexity of the solution is nln(n) for list sorting and n for the list length making it very close to linear time for most cases (such as your case size) –  frogeyedpeas Jul 4 '13 at 15:00
    
@vadim123: Quite right. I just assumed it would be trivial to adapt it; I should be more careful. Thanks for catching this. –  Eric Kightley Jul 4 '13 at 15:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.