For some G and N, there exists an optimal function/algorithm in the domain [0, G] which can decide if its argument is equal to N by checking the value of only V binary digits. Given G and N, how can I get the smallest possible value of V?
Example: G = 129, N = 128, the algorithm can be written as:
- Is the 128s place set? If not, unequal.
- Is the 1s place set? If so, unequal.
- Otherwise, equal.
The answer is 2 because 2 places were checked (128s and 1s). Values above 129 are outside the domain of the algorithm and are irrelevant, so they don't need to be checked.
For anyone wondering what the problem is trying to state, it's the following:
Given G and 0 <= N <= G, what is the fewest number of bits you need to check such that if, forall 0 <= x <= G. N = x at those bits, then N = x at all bits?
Example: if G=9 and N=5 then you need to check the 1-place, 2-place and 4-place bits. If G=129 and N=128 then you need to check the 1-place and 128-place bits.
The answer happens to be that only the bits of N where flipping it results in a number that is <= G have to be checked. The proof of that is as follows:
For each bit in N, if flipping that bit in N makes it <= G then we have to check it, because if we do not then N with the bit flipped passes the checks while still being one of the numbers in the set of possibilities. From this follows we have to check each 1-bit from N, since flipping it makes the result <=N which is <=G . If flipping a bit from N makes it > G then we do not have to check it because we already check every 1-bit so if the bit we do not check is flipped the smallest that number could be is N with that bit flipped which is bigger than G and thus isn't in the set of possibilities.