Ankur's Blog: Datastructure

BST has some basic operation like Search, Insert, Delete, Traversal (In-order, pre-order, post-order).If we want to delete a node from BST, Firstly we search this node and delete this node.

Now we make a BST using some data and following the BST properties. The data is given below:

47,40,54,38,30,39,49,60,57,80;

SUBXOR - SubXor

Ankur's BlogJanuary 30, 2019Codechef, Datastructure, Online Judge, Spoj, Trie Tree No comments

SUBXOR - SubXor

Subarray Xor

Topic: Trie Tree

Explanation

Solution 01:

#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 200005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;


struct trie
{
  int L,R;
  int lft, rgt;

  trie(){
    L = R = 0;
    lft = rgt = -1;
  }
};

int Index = 0;

void Insert(int value, int idx, int depth, trie *tree)
{
  for(int i = depth-1; i >= 0; i--){
    int bit = (value >> i ) & 1;
    if(bit){
      tree[idx].R++;
      if(tree[idx].rgt == -1){
        tree[idx].rgt = ++Index;
        idx = Index;
      }
      else idx = tree[idx].rgt;
    }
    else{
      tree[idx].L++;
      if(tree[idx].lft == -1){
        tree[idx].lft = ++Index;
        idx = Index;
      }
      else idx = tree[idx].lft;
    }
  }
}

int Query(int value, int cmp, int idx, int depth, trie* tree)
{
  int ans = 0;
  for(int i = depth-1; i >= 0; i--){
    int vBit = (value >>i) & 1;
    int cBit = (cmp >> i) & 1;
    if(cBit){
      if(vBit){
        ans += tree[idx].R;
        idx = tree[idx].lft;
      }
      else{
        ans += tree[idx].L;
        idx = tree[idx].rgt;
      }
    }
    else{
      if(vBit) idx = tree[idx].rgt;
      else idx = tree[idx].lft;
    }
    if(idx == -1)break;
  }
  return ans;
}

int main()
{
    FASTIO
    ///*
    //double start_time = clock();
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
    //*/
    int T;
    cin >> T;
    while(T--){
      trie tree[MAX];
      Index = 0;
      int n,k;
      cin >> n >> k;
      int XOR = 0;
      ll  ans = 0;
      Insert(0,0,20,tree);
      for(int i =0; i < n; i++){
        int x;
        cin >> x;
        XOR = XOR ^ x;
        ans += Query(XOR,k,0,20,tree);
        Insert(XOR,0,20,tree);
      }
      cout << ans << endl;
    }
    

    //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);

    return 0;
}

Solution 02

Solution 03

Video Conference

Ankur's BlogJanuary 30, 2019Datastructure, Hackerrank, Online Judge, Trie Tree No comments

Video Conference

Topic: trie

vector<string> solve (vector<string> names)
{
  unordered_set<string> s;
  unordered_map<string, int> mp;
  vector<string>ans;
  for(const auto& name: names){
    auto it = mp.find(name);
    if(it != mp.end()){
      it->second++;
      ans.push_back(name + ' ' + to_string (it->second));
    }
    else{
      mp[name] = 1;
      string t;
      bool inserted = false;
      for(auto c : name){
        t += c;
        auto p = s.insert(t);
        if(!inserted && p.second){
          inserted = true;
          ans.push_back(t);
        }
      }
      if(!inserted) ans.push_back(t);
    }
  }
  return ans;
}

Another Solution

4682 - XOR Sum

Ankur's BlogJanuary 30, 2019Datastructure, ICPC, Trie Tree No comments

4682 - XOR Sum

Topic : Trie Tree

N.B: Output not print in a single line ):

Solution 01:

#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 10005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
#define INT_SIZE 32

struct TrieNode
{
  int value;
  TrieNode *ar[2];
};

TrieNode *newNode()
{
  TrieNode *temp = new TrieNode;
  temp->value = 0;
  temp->ar[0] = temp->ar[1] = NULL;
  return temp;
}

void insert(TrieNode *root, int pre_xor)
{
  TrieNode *temp = root;

  for(int i = INT_SIZE - 1; i >= 0; i--){
    bool val = pre_xor & (1 << i);
    if(temp->ar[val] == NULL)
      temp->ar[val] = newNode();
    temp = temp->ar[val];
  }

  temp->value = pre_xor;
}

int query(TrieNode *root, int pre_xor)
{
  TrieNode *temp = root;
  for(int i = INT_SIZE - 1; i >= 0; i--){
    bool val = pre_xor & (1 << i);
    if(temp->ar[1-val] != NULL)
      temp = temp->ar[1-val];
    else if(temp->ar[val] != NULL)
      temp = temp->ar[val];
  }
  return pre_xor ^ (temp->value);
}


int maxSubarrayXOR(int ar[], int n)
{
  TrieNode *root = newNode();
  insert(root, 0);

  int res = INT_MIN, pre_xor = 0;
  for(int i = 0; i < n; i++){
    pre_xor = pre_xor ^ ar[i];
    insert(root, pre_xor);

    res = max(res, query(root, pre_xor));
  }
  return res;
}

int main()
{
    //FASTIO
    ///*
    //double start_time = clock();
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
    //*/
    int T;
    cin >> T;
    while(T--){
    int n;
    cin >> n;
    int a[n+2];
    for(int i = 0; i < n; i++){
      cin >> a[i];
    }

    cout << maxSubarrayXOR(a,n) << endl;;
   // if(T != 0) cout << " ";
  }

    //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);

    return 0;
}

Another Solution help from Raihan Ruhin blog ( Using Array)