• 145.6k
• 22
• 190
• 479

• 2.8k
• 2
• 24
• 42

• 2.8k
• 2
• 24
• 42

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 N % 2 = 1 ( N is an odd number )
0 Output Format

Output S, the number that occurs only once.

Sample Input:1

1
1

Sample Output:1

1

Sample Input:2

3
1 1 2

Sample Output:2

2

Sample Input:3

5
0 0 1 2 1

Sample Output:3

2

Explanation

In the first input, we see only 1 element and that element is the answer (1).
In the second input, we see 3 elements, 1 is repeated twice. The element that occurs only once is 2.
In the third input, 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 <vector>
#include <iostream>
#include <algorithm>
int main() {
 int size;
 std::cin >> size;
 if (size == 1) {
 int lone;
 std::cin >> lone;
 std::cout << lone << '\n';
 } else {
 std::vector<int> numbers(size);
 int index = 0;
 while (std::cin && index != size) {
 std::cin >> numbers[index++];
 }
 std::sort(numbers.begin(),numbers.end());
 for (std::size_t i = 1; i < numbers.size(); ++i) {
 if (numbers[i-1] != numbers[i] && numbers[i] != numbers[i+1]) {
 std::cout << numbers[i] << '\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?