The number that appears once
EasyStuck?
Show a hintHide the hint
Count how many times each number appears. Or exclusive-or the whole list together and see what survives.
The idea behind this problem
Next in this lesson
Most frequent numbersEvery number in the list appears exactly twice, except one which appears once. Find that one.
Worked example#
For [4, 1, 2, 1, 2], count how many times each number appears:
| number | times |
|---|---|
| 4 | 1 |
| 1 | 2 |
| 2 | 2 |
Only 4 appears once, so the answer is 4.
Counting works and is the obvious approach. There is also a trick worth knowing: exclusive-or of a number with itself is zero, and with zero is itself, so exclusive-or of the whole list leaves exactly the number that had no partner.
Constraints#
1 <= n <= 100000, and n is always odd- Every value appears twice except one
Input
nums is a count then that many integers.
Output
The single number.
Examples
Input
5 4 1 2 1 2
Output
4
1 and 2 both appear twice, so 4 is the odd one out.
Input
3 2 2 1
Output
1
Only 1 has no partner.
Input
1 7
Output
7
A single number is trivially the one that appears once.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.