Poor performance of code

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);
}

---

Perhaps the issue is at the level of the algorithm rather than the implementation. For example, perhaps it would be more efficient to sort the vector, then do a single pass to find the first number that does not have an adjacent paired value?

Thanks for your reply. Yes, it actually occurred to me to sort the vector first and check for adjacent equal pairs. However I think the problem requires a traversal of the whole vector because only one element is supposed not to have a counterpart. I also thought that I could do away with the for-loop I used in the first version.

Code:

---

// you can use includes, for example:
#include <algorithm>
#include <functional>
#include <vector>
#include <cassert>
#include <iostream>
#include <iterator>


int solution(std::vector<int> &A)
{
    const auto N = A.size();
    auto inRange = [](const int a) { return (a > 0) && (a <= 1000000); };
    if (N % 2 == 0 || !inRange(N))
    {
        return -1;
    }


    if (!std::is_sorted(std::begin(A), std::end(A)))
    {
        std::sort(std::begin(A), std::end(A));
    }
   
    auto odd{-99};
    auto it = A.begin();
    while (it != A.end())
    {
        if (!inRange(*it))
        {
            return -2;
        }
       
        if (*it == *(it + 1))
        {
            it = it + 2;
            continue;
        }
        odd = *it;
        ++it;
    }
    return odd;
}


int main()
{
    std::vector<int> v = {1, 7, 1, 8, 3, 7, 8};
    assert(solution(v) == 3);
    // std::cout << "The odd number is: " << solution(v) << "\n";
}

---

Quote:

---

Originally Posted by BroVic

However I think the problem requires a traversal of the whole vector because only one element is supposed not to have a counterpart.

---

That's precisely why you don't have to traverse the whole vector. Once you find an element that doesn't have an adjacent counterpart, you know for sure it is the odd element as long as the input parameters are satisfied.

I might suggest something like this:

Code:

---

int solution(std::vector<int>& numbers)
{
    if (numbers.size() % 2 == 0)
    {
        return -1;
    }

    for (const auto i : numbers)
    {
        if (!(i > 0 && i <= 1000000))
        {
            return -2;
        }
    }

    std::sort(std::begin(numbers), std::end(numbers));

    auto last_element_it = numbers.end() - 1;
    for (auto it = numbers.begin(); it != last_element_it; it += 2)
    {
        if (*it != *(it + 1))
        {
            return *it;
        }
    }
    return *last_element_it;
}

---

My reasoning:

• No point applying the range check to the size of the vector; you only care that it has an odd number of elements.
• Since we can stop early when finding the odd element, doing the range check for all elements before sorting would ensure we validate the entire input.
• On one hand, having the inRange function is good for readability. On the other hand, it is only used once, and the code obviously validates that the value is within a range, so I have removed the function.
• It seems unlikely that the input will be sorted, so there's no point checking if it is not sorted before sorting.
• Instead of checking for end() in the loop condition, we check for the iterator to the last element. This avoids the problem where you're at the last element, and then try to compare with *(it + 1) which does not exist.

Thanks again. The reason I created `inRange` is because one of the requirements of the task was to check the bounds of both the length of the array AND the value of each element in the array.

Wouldn't it be more sensible to check the number before you add it to the vector ?

Quote:

---

Originally Posted by thmm

Wouldn't it be more sensible to check the number before you add it to the vector ?

---

Makes sense, though the task was agnostic as to how the input vector was generated. Like I said originally, it was for a coding test and the emphasis was on both code correctness and efficiency.

Perhaps you could post a link to the site where you got the exercise from.

Most of these online exercise sites are crafted in such a way that the first program you think of will typically fail either the space or time requirement.
Basically, you win or lose based on the amount of thinking you did before you got to the point of writing "int main".

Quote:

---

Originally Posted by Salem

Perhaps you could post a link to the site where you got the exercise from.

Most of these online exercise sites are crafted in such a way that the first program you think of will typically fail either the space or time requirement.
Basically, you win or lose based on the amount of thinking you did before you got to the point of writing "int main".

---

It's Log in - Codility. You'd have to sign up though. It's the second exercise among the training tasks.