Algorithm to find minimum number of bits to distinguish a set of binary numbers

Question

Say we have K binary numbers (each of same length). We need to find minimum of number of bits needed (need not be continuous) to uniquely identify these K binary numbers. For example 100, 110 can be distinguished by 1 bit (at second position). 111, 110, 101 need 2 bits to be distinguished.

Answer 1

We can see those binaries as a set of linear equations. So, for example , if we have these binary : 1111, 1100, 1001, we can represent them as follow:

x1 + x2 + x3 + x4 = y1
x1 + x2 + 0  + 0  = y2
x1 + 0  + 0  + x4 = y3

From here, we realize that, we can use Gaussian elimination to reduce those equations to eliminate extra variables (in above example, it is x1). The result of the reduction will be set of K distinct variables, and we remove one extra variable to obtain the result of the original question.