I just did an online coding test and my code was said to be correct but performance is an issue. Could anyone help me improve it?
Code:
// C++ 14
// 'solution' checks an uneven-length array of integers (i.e. vector) wherein
// each element has a paired value, while the array has only one value that does not
// have a paired couterpart. That value that is a singleton should be returned by
// the function
#include <algorithm>
#include <vector>
#include <functional>
#include <cassert>
bool inRange(int a)
{
return (a > 0) && (a <= 1000000);
}
int solution(std::vector < int >&A)
{
auto N = A.size();
if (N % 2 == 0 || !inRange(N)) {
return -1;
}
for (const auto i:A) {
if (!inRange(i)) {
return -2;
}
}
std::vector < int >B {
};
int odd {
-99};
while (B.size() != N) {
// remove first number discovered
// after copying it to B
B.push_back(A.back());
A.pop_back();
const auto res = std::find(A.begin(), A.end(), B.back());
if (res != A.end()) {
B.push_back(*res);
A.erase(res); // 2nd number discovered so remove
continue;
}
odd = B.back();
}
return odd;
}
// Run example
int main()
{
std::vector < int >v = { 1, 7, 1, 8, 3, 7, 8 };
assert(solution(v) == 3);
}