TopCoder SRM 569 - Div I Lvl 1

We need to be able to find the Operation of each bit, i.e. whether it is OR, AND , XOR.

If you see the truth table for these operations:

A	B	OR	AND	XOR
0	0	0	0	0
0	1	1	0	1
1	0	1	0	1
1	1	1	1	0

You see that the first combination where both bits A/B are '0' all the results are zero, so this combination of bits doesn't help us identify the operation. => If we have bits 0,1,1 available to be inputted at a bit position we can identify the operation.

So, now the problem reduces to finding the no. of plates to be added so that there is a combination of 011 bits available at each position.


 def srm569(plates):
    more_plates_needed = 0
    M = len(plates[0])
    for i in range(0,M):
        bits_needed = ['0','1','1']
        for j in range(0,len(plates)):
            if plates[j][i] in bits_needed:
                bits_needed.remove(plates[j][i])
        more_plates_needed = max(more_plates_needed,len(bits_needed))
    return more_plates_needed


Examples:
=======

srm569(["01010101",
 "10101010"])
Out[34]: 1

srm569(["10010101011",
 "00010101001",
 "00100010111",
 "00101010101",
 "01010111101"])
Out[35]: 1

srm569(["1101001011010",
 "0010000010101",
 "1010101011110",
 "1101010100111",
 "1011111110111"])
Out[36]: 0