Hacker Rank - Lonely Integer

Question

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 < 100
• N % 2 = 1 ( N is an odd number )
• 0 <= A[i] <= 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 <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?

Answer 1

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.

Answer 2

I believe you can achieve it with just :

   int result;
   for (const auto& item : items)
   {  
       result ^= item;
   }

Documentation : for each

Answer 3

Improving Margus's Code, initialize the result with the first value; Here's the code snippet:

int result = -1;
size_t size = 0;
std::cin >> size;
int input = 0;
for(int i = 0; i < size; i++) {
    std::cin >> input;
    if( i == 0 ) {
        result = input;
    }
    else {
        result ^= input;
}
if(result == -1) {
    std::cout << "No number is lonely" << std::endl;
}
else {
    std::cout << "Lonely Number: " << result << std::endl;
}

Space Complexity : O(1)
Time Complexity : O(n), where n is the size

LINK for different version of the function (LonelyInteger)

As @mdfst suggested:

int LonelyInteger(vector < int > a, int overrider) {
    int tmp = a[0];
    for(int i = 1; i < a.size(); i++) {
        tmp ^= a[i];
    }    
    return tmp;
}

As for the explanation for initializing with the value that is an actual input rather than using some randomly picked number is that in case let's say we have

input as: 1 1 2 2 3 and my variable is initialized as

int result = 1;

It would actually lead to an incorrect output. So the sole reason for doing that was to make sure that my output stays correct irrelevant to the user input and I don't have to end up changing the value for the initialization; @mdfst

Answer 4

I would suggest a different but more general approach (aka in case the element is not a single number but a struct that cannot be xor'ed)

The idea would be to utilize a simple std::unordered_set. The following code should give the idea, assuming one can initialize the struct of type T from std::cin

std::unordered_set<T> pairs;
for (unsigned input = 0; input < numInputs; ++input) {
    T newStruct;
    std::cin >> newStruct;
    if (pairs.find(newStruct) == pairs.end()) {
        piars.insert(newStruct);
    } else {
        pairs.erase(newStruct);
    }  
}

if (pairs.empty()) {
    std::cout << "There is no lonely number.\n";
} else {
    std::cout << "The lonely number is " << pairs[0];
}