leetcode

commit 5a19b6d0e4927c1462e5beffeb6820ecbf4eeaf7
parent 3c9abce7a0156391f17fb7e03c4a7635375a1ae4
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue,  6 Feb 2024 17:14:36 +0000

1 Random Problem

Diffstat:
A
Problems/0421.cpp
 | 
46
++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 47 insertions(+), 0 deletions(-)
diff --git a/Problems/0421.cpp b/Problems/0421.cpp
@@ -0,0 +1,46 @@
+class Solution {
+    struct Node {
+        Node *child[2] = {nullptr, nullptr};
+    };
+
+    Node trie;
+
+    void insert(const int n) {
+        Node *crnt = ≜
+        bitset<32> bs = n;
+
+        for (int i = 31; i >= 0; i--) {
+            const auto c = bs[i];
+            if (!crnt->child[c]) crnt->child[c] = new Node();
+            crnt = crnt->child[c];
+        }
+    }
+
+    int find(const int n) const {
+        const Node *crnt = &trie;
+        bitset<32> bs = n;
+
+        int res = 0;
+        for (int i = 31; i >= 0; i--) {
+            const auto c = bs[i];
+            if (crnt->child[!c]) {
+                crnt = crnt->child[!c];
+                res += 1 << i;
+            } else {
+                crnt = crnt->child[c];
+            }
+        }
+        return res;
+    }
+
+  public:
+    int findMaximumXOR(const vector<int> &nums) {
+        for (const int n : nums)
+            insert(n);
+
+        int res = 0;
+        for (const int n : nums)
+            res = max(res, find(n));
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -314,6 +314,7 @@ for solving problems.
 |  0416  |   Medium   | [Partition Equal Subset Sum](Problems/0416.cpp)                                                    |
 |  0417  |   Medium   | [Pacific Atlantic Water Flow](Problems/0417.cpp)                                                   |
 |  0419  |   Medium   | [Battleships in a Board](Problems/0419.cpp)                                                        |
+|  0421  |   Medium   | [Maximum XOR of Two Numbers in an Array](Problems/0421.cpp)                                        |
 |  0424  |   Medium   | [Longest Repeating Character Replacement](Problems/0424.cpp)                                       |
 |  0427  |   Medium   | [Construct Quad Tree](Problems/0427.cpp)                                                           |
 |  0429  |   Medium   | [N-ary Tree Level Order Traversal](Problems/0429.cpp)                                              |