Lesson 2

There are only \(2^{2^n}\) Boolean functions on \(n\) variables, yet this number grows extremely fast: it is \(16\) for \(n=2\), \(256\) for \(n=3\), and \(65\ 536\) for \(n=4\). Exhaustive methods are therefore useful for discovering patterns on tiny instances, but they do not scale smoothly.

For up to three variables, every function has an optimal circuit that is also a formula: no intermediate result needs to be used twice. This permits a particularly simple dynamic program over truth tables.

Programming problem. Find the minimum number of gates needed to compute a Boolean function of at most three variables. All sixteen fan-in-two operations are allowed, and an input itself has size zero.

• Input format.  The first line contains \(n\) (\(1\le n\le3\)). The second line contains a bit string of length \(2^{n}\), the target truth table in lexicographic order.


• Output format.  Print the minimum number of gates.

2
0110

1

3
00010111

2

3
01101001

2