# How many NOTs are needed?

It’s relatively easy to see that we cannot compute an arbitrary Boolean function using only AND and OR gates. For example, even the NOT function cannot be computed using only those gates (why?).

Can we build a circuit to compute an arbitrary Boolean function using a constant number of NOT gates?

Solution to the “42 code golf” problem

This was my best result:

```n=1e6,m,c,d;main(){while(c+=d==42,d=0,m=--n)while(d+=m%10,m/=10);printf("%d\n",c);}
```

It would have been nice to find a solution under 80 bytes but, after one hour of trying, that was the best I could manage…

## 5 thoughts on “How many NOTs are needed?”

1. zeuxcg says:

82:
n=1e6,m,c,d;main(){while(d+=m%10,(m/=10)||(c+=d==42,d=0,m=–n));printf(“%d\n”,c);}

Arguably \n is not part of the problem so it’s 80 without it 😉

2. mchouza says:

Great solution!

3. zeuxcg says:

79 without \n (81 with):
n=1e6,m,c,d;main(){for(;(m/=10)||(c+=d==42,d=0,m=–n);d+=m%10);printf(“%d”,c);}

• mchouza says:

Nice. I was thinking about “clever” ways to brute force the problem but it seems out of reach even when making assumptions (some assumptions will be needed anyway to avoid `printf("6061")` being an answer 😀 ).

4. […] a previous post we have asked how many NOTs are needed to compute an arbitrary Boolean function. In this post we […]