srm386

CandidateKeys.cpp

class CandidateKeys {
public:
    int NumberOfSetBits(int i){
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }

    vector<int> getKeys(vector<string> table) {
        vector<int> ans;
        int R=table.size(),C=table[0].size(),A=11,B=-1,N=(1<<C);
        vector<bool> valid(N,true);
        for(int i=0;i<N;++i){
            if(!valid[i])
                continue;
            int len=NumberOfSetBits(i);
            set<string> keys;
            for(int r=0;r<R;++r){
                string t="";
                for(int c=0;c<C;++c){
                    if((1<<c)&i){
                        t+=table[r][c];
                    }
                }
                keys.insert(t);
            }
            if(keys.size()==R){//superkeys
                A=min(A, len);
                B=max(B, len);
                for(int j=i+1;j<N;++j){//remove superkey that't not candidate
                    if((i&j)==i){
                        valid[j]=false;
                    }
                }
            }
        }
        if(A!=11 || B!=-1) ans.assign({A,B});
        return ans;
    }
};