fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class TrieNode {
  5. public:
  6. 	vector<TrieNode*> m_children;
  7.  
  8. 	TrieNode() : m_children(2, nullptr) {}
  9.  
  10. 	~TrieNode() {
  11. 		delete m_children[0];
  12. 		delete m_children[1];
  13. 	}
  14.  
  15. 	TrieNode* createChilldIfNotPresent(int index) {
  16. 		if (m_children[index] == nullptr) {
  17. 			m_children[index] = new TrieNode;
  18. 		}
  19. 		return m_children[index];
  20. 	}
  21. };
  22.  
  23. class Trie {
  24.  
  25. private:
  26.     TrieNode* m_root{new TrieNode};
  27.  
  28. public:
  29.     Trie() = default;
  30.     ~Trie() { delete m_root; }
  31.     void insert(int num);
  32.     int maxXor(int num) const;
  33. };
  34.  
  35. void Trie::insert(int num) {
  36. 	auto currNode = m_root;
  37. 	int temp = 1 << 30;
  38.  
  39. 	for (int i = 30; i >= 0; --i) {
  40. 		if ((num & temp) > 0) {
  41. 			currNode = currNode->createChilldIfNotPresent(1);
  42. 		} else {
  43. 			currNode = currNode->createChilldIfNotPresent(0);
  44. 		}
  45. 		temp = temp >> 1;
  46. 	}
  47. }
  48.  
  49. int Trie::maxXor(int num) const {
  50. 	auto currNode = m_root;
  51. 	int temp = 1 << 30;
  52. 	int ans{};
  53.  
  54. 	for (int i = 30; i >= 0; --i) {
  55. 		if ((num & temp) > 0) {
  56. 			if (currNode->m_children[0] != nullptr) {
  57. 				ans = ans | temp;
  58. 				currNode = currNode->m_children[0];
  59. 			} else {
  60. 				currNode = currNode->m_children[1];
  61. 			}
  62. 		} else {
  63. 			if (currNode->m_children[1] != nullptr) {
  64. 				ans = ans | temp;
  65. 				currNode = currNode->m_children[1];
  66. 			} else {
  67. 				currNode = currNode->m_children[0];
  68. 			}
  69. 		}
  70. 		temp = temp >> 1;
  71. 	}
  72. 	return ans;
  73. }
  74.  
  75. int main() {
  76. 	// your code goes here
  77. 	vector<int> nums{3, 8, 2, 6, 4};
  78.  
  79. 	Trie trie;
  80. 	trie.insert(0);
  81.  
  82. 	int ans{};
  83. 	int xorVal{};
  84. 	for (int num : nums) {
  85. 		xorVal ^= num;
  86. 		trie.insert(xorVal);
  87. 		ans = std::max(ans, trie.maxXor(xorVal));
  88. 	}
  89.  
  90. 	cout << "Max xor = " << ans << endl;
  91. 	return 0;
  92. }
Success #stdin #stdout 0.01s 5460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max xor = 15
https://ideone.com/rMH3WA
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!