AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Brainteaser coding problems

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.

12 problems · 3 easy · 9 medium · judged by hidden tests in 13 languages

12problems

3 easy

9 medium

0 hard

Sign in to tick off what you solve.

Study plan: 10 problems · about 5 h 20 min

Start the study plan

Next up: Nim Game

How it works

Brainteaser, step by step

Bulb switcher: which bulbs stay on, with divisor counting

n = 10 bulbs; round i toggles every i-th bulb

before round 1: all off12345678910on: none (0)

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.

0:01 / 0:43Step 1 of 12
Transcript · 12 steps

Study plan

Learn brainteaser in 5 days

10 of the 12 Brainteaser problems (3 easy and 7 medium) over 5 days, about 5 h 20 min in all — the pattern first, then easiest to hardest. After that, the other 2 in the full list below are practice at your own pace. Then move on to String Matching.

  1. Day 1

    about 1 h 15 min

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

  2. Day 2

    about 1 h 10 min

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

  3. Day 3

    about 1 h 10 min

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

  4. Day 4

    about 1 h 10 min

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

  5. Day 5

    about 35 min

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

    Next topic: String Matching

Brainteaser Coding Problems: 12 Questions with Solutions

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

  • Problems: 12
  • By difficulty: 3 easy · 9 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

10 of the 12 Brainteaser problems (3 easy and 7 medium) over 5 days, about 5 h 20 min in all — the pattern first, then easiest to hardest. After that, the other 2 in the full list below are practice at your own pace. Then move on to String Matching.

Day 1

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

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 (3)

Medium (9)

Companies that ask brainteaser problems

Next topic: String Matching