Let's look at the numbers as bitstrings of length ~m~. For a number ~x~, let ~x^c~ be a number that has flipped binary representation.

For example, for ~m = 5~ and ~x = 13~ it follows ~x^c = 18~ because ~x = 01101_2~ and ~x^c = 10010_2~. Exactly ~x^c~ would be the ideal candidate for the biggest Hamming distance with ~x~, but ~x^c~ is not necessarily a part of ~a~.

Let us describe two possible solutions:

Solution 1

First solution is based on the fact that

$$\displaystyle \max_{y \in a} hamming(x, y) = m-\min_{y \in a} hamming(x^c, y)$$

Intuitively, we want a number as similar to ~x^c~ as possible.

Let us try to calculate the minimal Hamming distance for every number in ~[0, 2^m-1]~. For every number that appears in ~a~ it is ~0~. It leads us to a BFS solution, where each number in ~[0, 2^m-1]~ is a node in our graph and the edges represent changing exactly one bit. In a graph constructed in such a fashion Hamming distance between two numbers is exactly the length of shortest path between corresponding nodes. So we start BFS algorithm with every number from ~a~ in our queue and we will get the desired minimal distances.

Solution 2

Second solution is based on dynamic programming. Let ~popcount(x)~ be the number of ones in the binary representation of ~x~. The solution will be based on the following identity:

$$\displaystyle hamming(x, y) = popcount(x) + popcount(y) - 2 \cdot popcount(x \mathbin{\&} y)$$

Intuitively, each one in the binary representation of each number contributes ~1~ to Hamming distance, but then each common one decreases it by ~2~.

We want to calculate ~dp(mask)~ - maximum number of ones for some number in ~a~ but each one that is not in mask we penalize by ~2~. Formally,

$$\displaystyle dp(mask) = \max_{x \in a} (popcount(x) - 2 \cdot popcount(x \mathbin{\&} mask^c))$$

Then, the solution for some ~x~ will be given as ~popcount(x) + dp(x^c)~. The above ~dp~ can be calculated with standard dp with bitmasks methods.

Complexity of both solutions is ~\mathcal O(2^m \cdot m)~.