PATTERN 19: Bit Manipulation (XOR / Mask Thinking)

D

Qubits of DPK

April 11, 2026

Core DSA

Core Idea (lock this)

“Use bits to
You are not looping extra times.
You are compressing logic into bit operations.
If hashing stores state in memory,
bit manipulation stores state in bits.

How to Recognize This Pattern (CRITICAL)

You should instantly think Bit Manipulation when:
  • Numbers appear multiple times except one/few
  • You see:
  • Constraints mention:
  • The problem asks for:
Trigger phrases:
  • “appears once”
  • “every element appears twice except…”
  • “power of two”
  • “bitmask”
  • “subset generation”

30 MUST-DO INTERVIEW PROBLEMS

(10 Easy → 10 Medium → 10 Hard)

EASY (Bit Fundamentals)

Goal: XOR rules + bit properties must be automatic.
  1. #
    Single Number — LC 136
  2. #
    Missing Number — LC 268
  3. #
    Power of Two — LC 231
  4. #
    Number of 1 Bits — LC 191
  5. #
    Reverse Bits — LC 190
  6. #
    Hamming Distance — LC 461
  7. #
    Counting Bits — LC 338
  8. #
    Bitwise AND of Numbers Range — LC 201
  9. #
    Single Number II — LC 137
  10. #
    Single Number III — LC 260
Now EASY covers:
  • XOR cancellation
  • Bit counting
  • Rightmost set bit
  • Bit isolation trick
  • Power-of-two logic
No fluff like “swap without temp” — low interview value.

️ MEDIUM (Bitmask as State Compression)

Now bits represent choices.
  1. #
    Subsets (Bitmask View) — LC 78
  2. #
    Maximum Product of Word Lengths — LC 318
  3. #
    Find the Difference — LC 389
  4. #
    Gray Code — LC 89
  5. #
    Minimum Flips to Make a OR b Equal to c — LC 1318
  6. #
    Bitwise XOR of All Pairings — LC 2425
  7. #
    Count Triplets That Can Form Two Equal XORs — LC 1442
  8. #
    Total Hamming Distance — LC 477
  9. #
    Maximum XOR of Two Numbers — LC 421
  10. #
    Short Encoding of Words (bit view) — LC 820
Now MEDIUM locks:
  • Bitmask comparisons
  • Character compression into mask
  • Per-bit contribution thinking
  • XOR prefix logic

HARD (Mask DP / Advanced State Modeling)

Now we enter serious territory.
  1. #
    Minimum XOR Sum of Two Arrays — LC 1879
  2. #
    Shortest Path Visiting All Nodes — LC 847
  3. #
    Parallel Courses II — LC 1494
  4. #
    TSP (Bitmask DP) — GFG
  5. #
    N-Queens (Bitmask Optimization) — LC 51
  6. #
    Maximum Students Taking Exam — LC 1349
  7. #
    Beautiful Arrangement — LC 526
  8. #
    Can I Win — LC 464
  9. #
    Number of Good Subsets — LC 1994
  10. #
    Count Ways to Build Rooms in an Ant Colony — LC 1916
Now HARD demands:
  • dp[mask] definition
  • Mask transition logic
  • Bit iteration tricks
  • State compression intuition

The ONE Rule That Wins Interviews

Always be able to answer:
“What does
If you can’t explain the meaning of a bit,
you’re guessing.

Common Interview Mistakes

  • Using bit tricks without explanation
  • Overusing bit manipulation where clarity suffers
  • Forgetting integer overflow issues
  • Confusing XOR with OR

INTERVIEW REVISION CARD — Pattern 19

1️⃣ Pattern in One Line

"Compress logic into bits — encode state, detect uniqueness, and toggle properties in O(1)."

2️⃣ Recognize It When...

  • Numbers appear multiple times except one/few
  • Trigger words: "appears once", "every element twice except", "power of two", "bitmask", "subset"
  • O(1) space constraint mentioned
  • Subset/combination enumeration needed

3️⃣ Don't Confuse With...

  • Hashing (P2) → hashing uses memory; bit manipulation uses O(1) space
  • DP (P13) → bitmask DP uses bits as STATE; pure bit manipulation doesn't need DP table
  • Math → some bit tricks overlap with math — justify clearly which you're using

4️⃣ Approach in 3 Steps

  1. #
    Identify what each bit represents
  2. #
    Use XOR for cancellation, AND for masking, OR for setting, shift for position
  3. #
    Explain meaning of every bit operation — never guess

5️⃣ Invariant to Maintain

"At every step, the current bitmask accurately encodes the state of all elements processed so far."

6️⃣ Complexity to Justify

  • Time: O(N) for most bit problems, O(2^N) for bitmask DP
  • Space: O(1) for pure bit manipulation, O(2^N) for bitmask DP
  • Why: Bit operations are O(1) per element

7️⃣ Edge Cases to Always Check

  • Integer overflow — use long for large values
  • Negative numbers — right shift behavior differs
  • n = 0 — edge case for power of two, bit count
  • All zeros input
  • Single bit set vs multiple bits set

8️⃣ One Line to Say in Interview

"I'll use XOR/bitmask to encode state in O(1) space — XOR cancels paired elements, leaving only the unique one."