HackerRank‐Miscellaneous - a920604a/leetcode GitHub Wiki

long flippingBits(long n) {
    long ret = 0;
    for(int i=31;i>-1;--i){
        ret<<=1;
        int t = (n>>i)&1;
        ret+= (t ^ 1);
    }
    return ret;
}

string primality(int n) {
    if(n==1) return "Not prime";
    if(n==2 || n==3 || n==5 ) return "Prime";
    if(n%2==0 || n%3 ==0 || n%5 ==0  )  return "Not prime";
    for(int i=3;i<=n/i;++i){
        if(n%i==0) return "Not prime";
    }
    return "Prime";
}

class Node{
public:
  Node *zero, *one;
  void add(int num, int bits) {
      if(bits==-1) return ;
      if(( (num>>bits)&1) ==1){
          if (one == nullptr) one = new Node();
          one->add(num, bits-1);
      }
      else {
          if(zero == nullptr) zero = new Node();
          zero->add(num, bits-1);
      }
  }
  int get(int num, int bits){
      if(bits==-1) return 0;
      if((( (num>>bits)&1) ==0) && one || zero==nullptr){
          return (1<<bits) ^ one->get(num, bits-1);
      }
      else
        return (0<<bits) ^ zero->get(num, bits-1);
  }
};
// Complete the maxXor function below.
vector<int> maxXor(vector<int> arr, vector<int> queries) {
    // solve here
    vector<int> ret;
    Node *root= new Node();
    for(int a:arr) root->add(a, 30);
    for(int q:queries){
        ret.push_back( q^root->get(q, 30));
    }
    return ret;
}

class UF{
private:
    unordered_map<int, int> parent, size;
    int maxCount = 0;
public:
    void set(int n){
        if(parent[n]) return;
        parent[n]=-1;
        size[n]=1;
    }
    int find(int x){
        while(parent[x]!=-1){
            x = parent[x];
        }
        return x;
    }
    void unionSet(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot) return;
        if(size[pRoot] >= size[qRoot]){
            parent[qRoot] = pRoot;
            size[pRoot] +=size[qRoot];
            maxCount = max(maxCount, size[pRoot]);
        }
        else{
            parent[pRoot] = qRoot;
            size[qRoot] +=size[pRoot];
            maxCount = max(maxCount, size[qRoot]);
        }
    }
    int getmaxCount(){
        return maxCount;
    }
};
vector<int> maxCircle(vector<vector<int>> queries) {
    UF * uf= new UF();
    vector<int> ret;
    for(vector<int> q:queries){
        uf->set(q[0]);
        uf->set(q[1]);
        uf->unionSet(q[0], q[1]);
        ret.push_back(uf->getmaxCount());
    }
    return ret;
}