Recently I’ve been really addicted to GeoGuessr, and it’s a lot of fun learning about the distinct features of different countries around the world.

Currently I am study the poles around the world, there are some very similar pole in different country, so I have made some note on its feature and how to separate them.

This is not a hard question, but I find a surprising number of LeetCoders think it is a greedy question (which is not what I had in mind), and have written explanations to “prove” it.

Let’s take a look at their solutions and talk about what’s right and wrong with their reasoning.

I haven’t come across such a fun LeetCode problem in a long time. It doesn’t require any particularly hard prerequisite concepts, data structures, or algorithms, just basic knapsack dp knowledge is enough to solve it.

The trickiest (and most fun) part is figuring out how to recognize and convert it into a knapsack dp problem.

1. Introduction

   1. Setting
      Given an array $v$, find the maximum XOR of two numbers from array $v$.

   2. Brute-force Solution
      A trivial brute-force approach is $O(N^2)$: iterate over each pair of numbers and take the maximum XOR among all pairs.

   3. Idea
      A binary trie stores all the numbers in a trie data structure. For each number, we can find the maximum XOR against all other numbers in $v$ in $O(b)$ time, where $b$ is the number of bits. This reduces the overall complexity to $O(N\cdot b)$.