Project: Optimal Circuit Synthesis with SAT · Searching Small Circuits

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

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 binary string of length \(2^{n}\), the target truth table in lexicographic order.

Output format. Print the minimum number of gates.

This problem can only be submitted at Cogniterra.
Public samples
Public sample 1
Input
2
0110
Example output
1
Public sample 2
Input
3
00010111
Example output
4
Public sample 3
Input
3
01101001
Example output
2