Bitset instead of unordered_set vs Counting sort||beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nLC gives a hint\n> With the constraints, the length of the longest square streak possib
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLC gives a hint\n> With the constraints, the length of the longest square streak possible is 5.\n\nSince the constainst `2 <= nums[i] <= 10^5`, it\'s possible to use the bitset instead of unordered_set.\n\n2nd approach is similar to use counting sort which is also fast.\n\n3rd approach reconsider the upper bounds for max streak=5,4,3,2; that code optimizes the possiblity for the early stop. \n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Declare `long long N=100001` as a global variable\n2. Set `bitset<N> hasX=0`\n3. Set bit `hasX[x]=1` for x in nums\n4. Let `maxStreak=0`\n5. Proceed the loop\n```\nfor(long long x: nums){\n    int streak=1;\n    for(long long z=x*x; z<N; z*=z)// avoid of overflow\n        if (hasX[z]) streak++;\n        else break;\n    maxStreak=max(maxStreak, streak);// update maxStreak\n    if (maxStreak==5) break; //Early stop for 5 being the max\n}\n```\n6. if `maxStreak<2` return -1 otherwise return `maxStreak`\n7. The approach is using the argument in counting sort in which the used x in `nums` is unset avoiding of double computing. In 1st approach it\'s an unsorted array which can not be proceeded in such a way.\n# Why maxSreak<=5? Think how to furthermore optimize\nJust consider the small number 2. Just make squaring several times\n$$\n2, 2^2=4, 2^{2\\times 2}=2^4=16, 2^{4\\times 2}=2^8=256, 2^{8\\times 2}=2^{16}=65536\n$$\nThe square of $2^{16}=65536$ is $2^{32}$ which is $>10^5$\nThe upper bound for max streak beginning from 2 is 5\nIf $x=3$ then $3^8=6561$, the upper bound for max streak beginning from 3 is 4.\nIf $x=5$ then $3^8=390625$, the upper bound for max streak beginning from 5 is 3.\nIn fact, $\\sqrt[4]{100000}=17.782...$, when $x>=18$, the upper bound for max streak is just 2.\n\nA code using such facts is presented.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\nCounting sort: $O(n+N)$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(N)$$\n#  revised Code||C++ 0ms  beats 100% \nUsing the suggestion of @Sergei to find M=max(nums) during the 1st pass\n```cpp []\nconst long long N=100001;\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& nums) {\n        bitset<N> hasX=0;\n        int M=0;\n        for(int x: nums){\n            hasX[x]=1;\n            M=max(M, x);\n        }\n        int maxStreak=0;\n        for(long long x: nums){\n            int streak=1;\n            for(long long z=x*x; z<=M; z*=z)\n                if (hasX[z]) streak++;\n                else break;\n            maxStreak=max(maxStreak, streak);\n            if (maxStreak==5) break;\n        }\n        return maxStreak<2?-1:maxStreak;\n    }\n};\n```\n# C++ using argument in Counting sort||0ms beats 100%\nThe outer loop tests up to sqrt(M) thanks to suggestion of @Sergei\n```\nconst long long N=100001;\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& nums) {\n        bitset<N> hasX=0;\n        int M=0;\n        for(int x: nums){\n            hasX[x]=1;\n            M=max(M, x);\n        }\n        int maxStreak=0, Msqrt=sqrt(M);;\n        for(long long x=2; x<=Msqrt; x++){\n            if (hasX[x]==0) continue;\n            int streak=1;\n            for(long long z=x*x; z<=M; z*=z){\n                if (hasX[z]) {\n                    streak++;\n                    hasX[z]=0;\n                }\n                else break;\n            }\n            maxStreak=max(maxStreak, streak);\n            if (maxStreak==5) break;\n        }\n        return maxStreak<2?-1:maxStreak;\n    }\n};\n\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# 3rd C++ using upper bounds for max streak=5,4,3,2||0ms beats 100%\n```\nconst long long N=100001;\nconst int bound[]={2, 4, 17, 316};// bounds for early stop\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& nums) {\n        bitset<N> hasX=0;\n        int M=0;\n        for(int x: nums){\n            hasX[x]=1;\n            M=max(M, x);\n        }\n        int lim=5, i=0;\n        int maxStreak=0;\n        for(long long x=2; x<=bound[3]; x++){\n            if (hasX[x]==0) continue;\n            if (x>bound[i]) {\n                i++;\n                lim--;\n            }\n            int streak=1;\n            for(long long z=x*x; z<=M; z*=z){\n                if (hasX[z]) {\n                    streak++;\n                    hasX[z]=0;\n                }\n                else break;\n            }\n            maxStreak=max(maxStreak, streak);\n            if (maxStreak==lim) break;\n        }\n        return maxStreak<2?-1:maxStreak;\n    }\n};\n\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Array', 'Math', 'Bit Manipulation', 'Counting Sort', 'C++']