Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
702 B
1
Indexable
Never
class Solution {
public:   
    int maximumLength(vector<int>& arr) {
        long long res=1;
        if(arr.size()<3) return 1;
        map<int,int>mp;
        for(auto i:arr) mp[i]++;
        
        for(auto &i:mp){
            long long root= i.first;
            long long sum=0;

            if(root==1) {sum+=mp[root]; mp[root]=0;}
            while(root<INT_MAX && mp[root]>0){ //mp[root]>0 takes care of when root=1;
                sum+=2;
                if(mp[root]==1) break; //single occurence cnt continue more
                mp[root]=0;
                root=root*root;
            }
            if(sum%2==0) sum--;
            res=max(res,sum);
        }
        return res;
    }
};
Leave a Comment