Get started

Brainteaser Coding Problems: 9 Questions with Solutions

9 brainteaser coding problems — 2 easy · 7 medium — with solutions in 13 languages. Plus a step-by-step walkthrough and a 5-day plan.

  • Problems: 9
  • By difficulty: 2 easy · 7 medium
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

A brainteaser looks as if it needs a simulation or a search and turns out to need one observation: a bulb toggled once per divisor stays lit only at a perfect square; the XOR over every pairing keeps a list's XOR only when the other list has odd length; a game is decided by n modulo 4. The code is often a line or two. The problems here practise finding that observation — working small cases by hand, asking what an operation cannot change — and checking it before trusting it.

How brainteaser works, step by step

after 10 rounds: on = perfect squares ≤ 10112123134124515612367178124891391012510on: 1, 4, 9 (3)
Bulb switcher: which bulbs stay on, with divisor counting. Example: n = 10 bulbs; round i toggles every i-th bulb
  1. Ten bulbs start off. In round i every i-th bulb is toggled, so bulb k is toggled once for each divisor of k; the numbers under each bulb will list the rounds that touched it.
  2. Round 1 toggles every bulb, so all 10 are on. No later round divides 1, so bulb 1 is now final: 1 toggle (1), odd, so it stays on.
  3. Round 2 toggles 2, 4, 6, 8 and 10, switching them all off. No later round divides 2, so bulb 2 is now final: 2 toggles (1, 2), even, so it stays off.
  4. Round 3 toggles 3, 6 and 9: 6 comes on and 3 and 9 go off. No later round divides 3, so bulb 3 is now final: 2 toggles (1, 3), even, so it stays off.
  5. Round 4 toggles 4 and 8, switching them all on. No later round divides 4, so bulb 4 is now final: 3 toggles (1, 2, 4), odd, so it stays on.
  6. Round 5 toggles 5 and 10: 10 comes on and 5 goes off. No later round divides 5, so bulb 5 is now final: 2 toggles (1, 5), even, so it stays off.
  7. Round 6 toggles only bulb 6, since 2 × 6 > 10; it goes off. No later round divides 6, so bulb 6 is now final: 4 toggles (1, 2, 3, 6), even, so it stays off.
  8. Round 7 toggles only bulb 7, since 2 × 7 > 10; it goes off. No later round divides 7, so bulb 7 is now final: 2 toggles (1, 7), even, so it stays off.
  9. Round 8 toggles only bulb 8, since 2 × 8 > 10; it goes off. No later round divides 8, so bulb 8 is now final: 4 toggles (1, 2, 4, 8), even, so it stays off.
  10. Round 9 toggles only bulb 9, since 2 × 9 > 10; it goes on. No later round divides 9, so bulb 9 is now final: 3 toggles (1, 3, 9), odd, so it stays on.
  11. Round 10 toggles only bulb 10, since 2 × 10 > 10; it goes off. No later round divides 10, so bulb 10 is now final: 4 toggles (1, 2, 5, 10), even, so it stays off.
  12. Only bulbs 1, 4 and 9 are on — the perfect squares. Divisors pair up as d and k / d, and only a square has one divisor without a partner (its root), so only squares are toggled an odd number of times. The answer is ⌊√10⌋ = 3, in O(1) instead of an O(n log n) simulation.

Brainteaser study plan

All 9 Brainteaser problems (2 easy and 7 medium) over 5 days, about 5 h in all — the pattern first, then easiest to hardest. Then move on to String Matching.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Next topic: String Matching

Brainteaser: the essentials

When to reach for it

The brute force simulates n rounds or sums over every pair or triple, n reaches 10⁵ or 10⁹, and yet the problem is too plain to want a data structure. Odd operations ("replace nums[i] with nums[i] AND (nums[i] XOR x)"), rounds of toggles and games with perfect play are typical; games have their own page, Game Theory.

The pattern

Write the brute force, run it for n from 1 to 20, and study the table. Then ask what the operation cannot change — a parity, a bit that can only be cleared, a total — or how often each element contributes. In Bulb Switcher, bulb i is toggled once per divisor of i; divisors pair up as d and i ÷ d except a square root, so only perfect squares stay on: ⌊√n⌋ of them.

from math import isqrt

def bulbs_on_brute(n):              # the simulation, for small n
    on = [False] * (n + 1)
    for step in range(1, n + 1):
        for i in range(step, n + 1, step):
            on[i] = not on[i]
    return sum(on)

def bulbs_on(n):                    # odd number of divisors: perfect squares
    return isqrt(n)

Cost

The observation turns O(n²) or O(n × rounds) into O(n) or O(1). The brute force runs only on small cases: its job is to find the pattern and check it.

Common mistakes

  • Trusting a pattern seen in four or five cases; compare the formula with the simulation on twenty.
  • int(sqrt(n)) can be off by one for large n; use an integer square root such as Python's isqrt.
  • Edge cases the formula treats differently: n = 0, n = 1, an empty array.
  • In XORs over all pairs, reasoning about values instead of how often each appears; XOR keeps only each count's parity.

Start with

All brainteaser problems

Easy (2)

Medium (7)

Companies that ask brainteaser problems

  • Amazon 9 problems on brainteaser
  • Google 7 problems on brainteaser
  • Adobe 3 problems on brainteaser
  • Uber 2 problems on brainteaser
  • Arcesium 1 problem on brainteaser
  • Bloomberg 1 problem on brainteaser
  • Meta 1 problem on brainteaser
  • Microsoft 1 problem on brainteaser

Next topic: String Matching