Hacker Rank - Lonely Integer This is the problem statement for Lonely Integer.


  There are N integers in an array A. All but one integer occur in
  pairs. Your task is to find out the number that occurs only once. 
  
  Input Format
  
  The first line of the input contains an integer N indicating number of
  integers.   The next line contains N space separated integers that
  form the array A. 
  
  Constraints
  
  
  1 &lt;= N &lt; 100
  N % 2 = 1 ( N is an odd number )
  0 &lt;= A[i] &lt;= 100, ∀ i ∈ [1, N]
  
  
  Output Format
  
  Output S, the number that occurs only once. 
  
  Example 1
  
  Input

1
1

  
  Output

1

  
  We see only 1 element and that element is the answer (1).
  
  Example 2
  
  Input

3
1 1 2

  
  Output

2

  
  We see 3 elements, 1 is repeated twice. The element that occurs only
  once is 2.
  
  Example 3
  
  Input

5
0 0 1 2 1

  
  Output

2

  
  We see 5 elements, 1 and 0 are repeated twice. And the element that
  occurs only once is 2.


//I did not do the constraints
#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;algorithm&gt;

int main() {
    int size;
    std::cin &gt;&gt; size;
    if (size == 1) {
        int lone;
        std::cin &gt;&gt; lone;
        std::cout &lt;&lt; lone &lt;&lt; '\n';
    } else {
        std::vector&lt;int&gt; numbers(size);
        int index = 0;
        while (std::cin &amp;&amp; index != size) {
            std::cin &gt;&gt; numbers[index++];
        }
        std::sort(numbers.begin(),numbers.end());
        for (std::size_t i = 1; i &lt; numbers.size(); ++i) {
            if (numbers[i-1] != numbers[i] &amp;&amp; numbers[i] != numbers[i+1]) {
                std::cout &lt;&lt; numbers[i] &lt;&lt; '\n';
                break;
            }
        }
    }
}



Is this fast enough for extremely large elements? How to make this faster?
Can this be done efficiently without sorting?
How can I improve this code?
Disclaimer : this is not a proper code review.

A different algorithm

There is a O(n) in time and O(1) in space algorithm (and one can easily see that a smaller complexity cannot be achieved).

You just need to XOR all elements so that the one in pairs cancel each other and you are left with the lonely integer.