C++ | BEGINNER FRIENDLY | BINARY SEARCH | INTUITIVE
\n# Intuition\nSince we are changing the order of final subsequence (i.e. Sort)\nWe can sort the whole vector initially for our benefit to use binary search(i.e
![adobe_1st_Day.jpeg](https://assets.leetcode.com/users/images/0c36396f-5720-49e4-8d4a-060661360b47_1730084625.8143566.jpeg)\n# Intuition\nSince we are changing the order of final subsequence (i.e. Sort)\nWe can sort the whole vector initially for our benefit to use binary search(i.e. lower_bound for searching next element in the subsequence)\n\nSo what we can do , find all the subsequence starting from unique number , for that we can use a visited vector , to check whether it is not used in earlier subsequence , because longest will be the earlier one (Think yourself).\n\n# Approach\n1. Initialize vector<int>vis(n,0).\n2. sort(nums.begin(),nums.end()).\n3. For nums[i] not visited , get possible subsequence for this and mark the next subsequence element index (if found) through out the process.\n4. For finding next square of curr element we are using lower bound , and when we dont have next square of curr present in the array we are breaking the while(1) loop .\n5. After finding the longest possible sequence starting at index i , we update the longest variable that store the longest sequence according to problem . \n6. if (longest<2)return -1 . Said in problem statement\n\n# Complexity\n- Time complexity:\nO(NLOGN)\n\n- Space complexity:\nO(N)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    void getSequence(vector<int>&nums,long long start,int &temp_long,vector<bool>&vis){\n        start=start*start;\n        while(1){\n            auto it = lower_bound(nums.begin(),nums.end(),start);\n            if(it!=nums.end() && start==(*it)){\n                start*=start;vis[it-nums.begin()]=1;\n                temp_long++;\n            }\n            else break;\n        }\n    }\n    int longestSquareStreak(vector<int>& nums) {\n        int n = nums.size();\n        vector<bool>vis(n,0);\n        int longest = 0 ,temp_long=0;\n        sort(nums.begin(),nums.end());\n\n        for(int i=0;i<n;i++){\n            if(!vis[i] || (i>0 && nums[i]!=nums[i-1])){\n                vis[i]=1;\n                temp_long=1;\n                getSequence(nums,nums[i],temp_long,vis);\n                longest=max(longest,temp_long);\n            }\n        }\n        if(longest<2)return -1;\n        return longest;\n    }\n};\n```
['Math', 'Binary Search', 'Sorting', 'C++']