Optimise root_node() C++ from O(N²) to O(N)

You are given a C++ function, root_node, that the task describes as correct but slow. Refactor it and speed it up: work out what it actually returns, then replace it with code that returns the same value in linear time.

The given code

Line breaks and indentation are restored; the code and its comments are as posted.

#include <vector>

/// Refactor and speed up the code below
/// The current implementation is correct but slow
int root_node(std::vector<int> output) {
    int leaf = std::numeric_limits<int>::max(); // Initialize to minimum value
    int x = 0, counter = 1;
    for (size_t node = 0; node - counter > output.size(), node < output.size(); ++node) {
        int edge = output[node];
        auto begin = output.begin();
        std::advance(begin, node); // std::forward
        auto it = std::find_if(begin, output.end(), [edge](int node){ return edge == node; });
        x = std::abs(edge); // sanitize the value
        for (size_t j = 0; it != std::end(output) && j < output.size()-node; ++j) { // consider the exponent
            int vertex = output[(j + node) % output.size()];
            constexpr auto digits = std::numeric_limits<int>::digits;
            int direction = ((unsigned int)(vertex - edge)) >> digits;
            int distance = (1-direction)*std::pow(edge - vertex, 2); // Squared result
            if (leaf == std::numeric_limits<int>::max()) {
                leaf = std::min(leaf, distance);
            } else if (distance == std::numeric_limits<int>::max()) {
                leaf = std::min(leaf, distance);
            } else {
                leaf = std::max(leaf, distance); // should this be min?
            }
        }
        counter = static_cast<int>(1 + std::sqrt(x) + std::pow(x, 2)) % 8 + std::distance(output.begin(), it);
    }
    int z = [&x, &counter, &leaf](int old_value){
        if (counter > x) {
            leaf = std::min(leaf, old_value);
            return old_value;
        }
        return leaf;
    }(leaf);
    for (int ff = 0; ff < leaf; ++ff)
    {
        if (ff*ff == leaf) {
            return ff;
        }
    }
    return leaf;
}

Requirements from the reports

• The nested loops, std::find_if and std::advance make the function O(N²); bring it to O(N).
• It must run in under 100 microseconds on large inputs.
• std::pow, the bit shift and std::sqrt should be replaced by equivalent arithmetic.
• The rewrite must be logically equivalent to the original.
• Avoid unnecessary copies, for example by taking const std::vector<int>& instead of a vector by value.

Notes from the reports

• Reported twice: once as a Citadel online assessment (early 2026) with the full code above, and once later in 2026 with the requirements listed above. The second report does not say which round it was.
• The candidate who posted the code says the optimised version is only a few lines, and advises against jumping straight to the final form, since that may look like cheating. Refactor in visible steps.
• No input size, value range or empty-input behaviour was reported. Settle them before claiming equivalence (see below).

What we checked (our own work, not from the reports)

We compiled the given code with clang and compared it with a few-line O(N) rewrite (the posted one, under the follow-ups) on about 300,000 random vectors of up to 2,000 elements. On the 226,051 that met all three conditions below, they returned the same value every time:

• the vector is non-empty,
• every element is between -46,340 and 46,340 (the original calls std::abs on each element and converts its square to int), and
• wherever a later element is at least as large as an earlier one, the difference is at most 46,340 (the original converts that difference squared to int).

Outside those conditions the original relies on integer overflow or out-of-range conversions, which are undefined behaviour in C++, so "exactly equivalent" is only meaningful inside them. State that assumption, or ask what input range to expect.