# XOR using NAND gates

Source: https://www.techinterview.org/post/489166573/xor-using-nand-gates/
Updated: 2026-04-16 · techinterview.org

Create an XOR gate using only NAND gates.  (BTW, mostly all circuit problems assume you have two inputs plus 0 and 1 also as inputs).

### Solution

You may be able to find the solution [on the discussion forum](http://discuss.techinterview.org/?interview).

## 2026 Update: Logic Gate Design — NAND is Functionally Complete

NAND is a **functionally complete** gate: you can build any Boolean function using only NAND gates. This is why modern CPUs are built from NAND gates at the transistor level.

Building XOR from NAND: XOR(A,B) = (A NAND (A NAND B)) NAND (B NAND (A NAND B)). This takes 4 NAND gates.


```
def NAND(a, b):
    return not (a and b)

# NOT using NAND: NOT(A) = NAND(A, A)
def NOT(a):
    return NAND(a, a)

# AND using NAND: AND(A,B) = NOT(NAND(A,B))
def AND(a, b):
    return NOT(NAND(a, b))

# OR using NAND: OR(A,B) = NAND(NOT(A), NOT(B)) [De Morgan's law]
def OR(a, b):
    return NAND(NOT(a), NOT(b))

# XOR using 4 NAND gates
def XOR_via_NAND(a, b):
    nand_ab = NAND(a, b)           # Gate 1
    nand_a_nab = NAND(a, nand_ab)  # Gate 2
    nand_b_nab = NAND(b, nand_ab)  # Gate 3
    return NAND(nand_a_nab, nand_b_nab)  # Gate 4

# Verify truth table
print("A  B  XOR  NAND-based")
for a in [False, True]:
    for b in [False, True]:
        expected = a ^ b
        result = XOR_via_NAND(a, b)
        print(f"{int(a)}  {int(b)}  {int(expected)}    {int(result)}  {'✓' if expected == result else '✗'}")

# Gate count optimization:
# XOR from 4 NANDs  (minimum proven optimal)
# XOR from 5 NORs
# XOR from 7 AND/OR/NOT gates without restriction

# Real-world: NAND flash memory uses the same principle —
# NAND gates are cheaper to manufacture than AND gates
print("nNAND flash: the same NAND that's functionally complete")
print("is also the dominant storage technology in SSDs and phones")
```

**Interview angle:** This question appears in hardware design, FPGA programming, and systems interviews. The deeper question is: "Why is NAND universal?" Answer: because any truth table can be expressed as AND, OR, NOT — and all three can be built from NAND. Connects to **computational universality** and why a single primitive operation (like NAND or NOR) can compute anything.