Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define int long long
- class Node
- {
- public:
- Node * child[2];
- Node()
- {
- child[0] = NULL;
- child[1] = NULL;
- }
- };
- // time complexity = N * log2(max(A[i]))
- void insert(Node * root, int x)
- {
- for(int i = 32; i >= 0; i--)
- {
- int bit = ((x >> i) & 1);
- if(root -> child[bit] == NULL)
- {
- root -> child[bit] = new Node();
- }
- root = root -> child[bit];
- }
- }
- //time complexity = N * log2(max(A[i]))
- int maXxor(Node * root, int y)
- {
- int ret = 0;
- for(int i = 32; i >= 0; i--)
- {
- int bit = ((y >> i) & 1);
- if(root -> child[bit ^ 1] == NULL)
- {
- root = root -> child[bit];
- }
- else
- {
- ret |= (1LL << i);
- root = root -> child[bit ^ 1];
- }
- }
- return ret;
- }
- // space complexity is nlogn;
- int32_t main()
- {
- int n;
- cin >> n;
- vector<int> arr(n);
- Node * root = new Node();
- int ans = 0;
- for(int i = 0; i < n; i++)
- {
- cin >> arr[i];
- int y = arr[i];
- insert(root, arr[i]);
- int temp = maXxor(root, y);
- ans = max(ans, temp);
- }
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement