Explanation

First pair the $$$128$$$ bits into $$$64$$$ pairs and calculate the OR of each pair. If there is an anomaly, at least $$$2$$$ pairs will have an OR of $$$1$$$.

Construct a tripartite graph, where the three parts have sizes $$$4$$$, $$$5$$$ and $$$5$$$ respectively. Call the parts $$$A$$$, $$$B$$$, $$$C$$$. This graph has a total of $$$4 \times 5 + 4 \times 5 + 5 \times 5 = 65$$$ edges. Assign each bit to one of these edges, so there is $$$1$$$ unused edge.

For each vertex, calculate the OR of all edges that include it. Define a vertex to be active if this OR is equal to $$$1$$$. Then, we either have:

• All three parts have active nodes, or
• There exists a part with two active nodes

if and only if there is an anomaly.

Given a part with $$$X$$$ nodes, we can check both:

• whether it has an active node
• whether it has $$$\geq 2$$$ active nodes

using $$$3X - 4$$$ operations as follows. Suppose the nodes are $$$A_1, A_2, \cdots, A_X$$$.

1. Calculate $$$P_i = A_1 \bigvee A_2 \bigvee \cdots \bigvee A_i$$$. This can be done by letting $$$P_1 = A_1$$$ and $$$P_i = P_{i-1} \bigvee A_i$$$. Note $$$P_X$$$ is $$$1$$$ if and only if there is at least one active node.

2. Calculate $$$P_i \bigwedge A_{i+1}$$$ for each $$$1 \leq i \lt X$$$. Note that if the component has at least two active nodes, $$$P_i \bigwedge A_{i+1} = 1$$$ for some $$$i$$$.

3. Take the OR of these $$$X-1$$$ values.

Step $$$1$$$ requires $$$X-1$$$ gates, step $$$2$$$ requires $$$X-1$$$, and step $$$3$$$ requires $$$X-2$$$ gates, for a total of $$$3X - 4$$$.

Overall, we need:

• $$$64$$$ gates to compute the ORs of pairs
• $$$\sum_{\text{node } v} (\text{deg}(v) - 1) = 2 E - V = 2 \times 64 - 14 = 114$$$ gates to compute whether each node is active
• $$$3 \times |A| - 4 = 8$$$ gates to compute $$$f_A$$$, which is $$$1$$$ if $$$A$$$ has at least one active node, and $$$g_A$$$, which is $$$1$$$ if $$$A$$$ has at least two active nodes
• $$$3 \times |B| - 4 = 11$$$ and $$$3 \times |C| - 4 = 11$$$ gates to do the same for $$$B$$$ and $$$C$$$
• $$$5$$$ gates for the expression $$$g_A \bigvee g_B \bigvee g_C \bigvee (f_A \bigwedge f_B \bigwedge f_C)$$$

Which adds up to $$$64 + 114 + 8 + 11 + 11 + 5 = 213$$$ gates.

Once again, congratulations ChatGPT!