Find the Maximum Number of Elements in Subset — Editorial

Opening the reading…

Intuitionwhy every value in the middle needs a pair

For a starting value x greater than 1, a valid sequence looks like x, x squared, x to the fourth power, and so on, followed by the same values in reverse order. The first and last values appear once, while every value strictly between them appears twice. Therefore, extending a chain by one level always consumes two copies of the current value and needs at least one copy of its square.

You can try every distinct value as the first value of a chain. Start with a sequence of length 1, then repeatedly square the current value. If the current value has at least two copies and its square exists, that square becomes the new endpoint and the sequence grows by two. The counts do not need to be modified because each starting value is an independent candidate; you only need the largest candidate.

The value 1 breaks the usual growth pattern because squaring it never changes it. A valid sequence containing only 1s has odd length, so you can use all of them when their count is odd, or one fewer when their count is even. This case is handled directly instead of entering the repeated-squaring loop.

Approach

Build a frequency map for every number in nums, because the sequence is determined by both which squared values exist and how many copies each value has.

Initialize the answer from the count of 1s, using the largest odd number no greater than that count, because a chain made entirely of 1s must have odd length.

Try every distinct value greater than 1 as a possible chain start, because the best subset may begin at any value and there is no need to choose the smallest value globally.

Set the current value to the starting value and the current length to 1, because a single available value always forms a valid sequence by itself.

While the current value has at least two copies, square it using long long and check whether the square is present, because the current value becomes an interior pair and the square must become the next endpoint.

When the square exists, increase the length by 2 and move to the square, because one copy of the new value goes on each side of the center path.

Stop when the current value has fewer than two copies, its square is absent, or its square exceeds the input limit, because no further symmetric extension can be formed; then update the maximum with this chain length.

Complexitythe chain height is tiny because squaring grows rapidly

MEASURE	BOUND	WHY
Time	O(n log log V), which is O(n) for V <= 10^9	Building the frequency map takes O(n). Each of the u distinct values is tested, and repeated squaring gives at most O(log log V) levels before the value exceeds V; each level uses constant-time hash lookups. No element is scanned once per chain.
Space	O(u) extra space	The frequency map stores one entry per distinct value, and the temporary chain state is constant size. The returned integer is output rather than working memory, so it is excluded from the bound; in the worst input shape, all n values are distinct and u = n.

Here n is the number of elements, V is the largest value in nums, and u is the number of distinct values. Under the given limit V <= 10^9, log log V is bounded by a small constant.

Annotated solutionC++ · frequency map with repeated squaring

CPPCount frequencies, grow each square chain by two elements, and handle 1s separately.

#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int value : nums) {
            ++count[value];
        }

        int answer = 1;

        auto ones = count.find(1);
        if (ones != count.end()) {
            int onesLength = ones->second;
            if (onesLength % 2 == 0) {
                --onesLength;
            }
            answer = max(answer, onesLength);
        }

        for (const auto& entry : count) {
            int start = entry.first;
            if (start == 1) {
                continue;
            }

            long long current = start;
            int length = 1;

            while (true) {
                auto currentIt = count.find(static_cast<int>(current));
                if (currentIt == count.end() || currentIt->second < 2) {
                    break;
                }

                long long next = current * current;
                if (next > 1000000000LL) {
                    break;
                }

                auto nextIt = count.find(static_cast<int>(next));
                if (nextIt == count.end()) {
                    break;
                }

                length += 2;
                current = next;
            }

            answer = max(answer, length);
        }

        return answer;
    }
};

The condition currentIt->second < 2 is the key placement in the loop. The current value is already the endpoint of the chain, so it needs only one copy at first. It needs two copies before you extend, because extension places one copy on each side of the eventual center. The next value needs only one copy immediately; it will be required twice only if the chain grows again.