Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Two stages. First count the number of ways M to tile a 4×n wall using 4×1 (and 1×4) bricks — this is a Fibonacci-like recurrence: f(0)=f(1)=f(2)=f(3)=1 and f(n) = f(n−1) + f(n−4) for n ≥ 4 (place a vertical brick and reduce by 1 column, or place four horizontal bricks filling the next 4 columns and reduce by 4). Then count how many prime numbers are ≤ M using a Sieve of Eratosthenes. The answer is that prime count. Tiling is O(n); the sieve is O(M log log M).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you derive the f(n)=f(n−1)+f(n−4) tiling recurrence with the correct four base cases, then compose it with an efficient prime count.
Where candidates slip
Using a step of 2 (f(n)=f(n−1)+f(n−2)) as if it were a 2×n board, wrong base cases, or returning M instead of the count of primes ≤ M.
How to stand out
Explain why the horizontal move consumes exactly 4 columns (a full layer), enumerate the four base cases, and use a sieve (not trial division) for the prime count.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Count tilings with a Fibonacci-like recurrence, then count primes up to that count.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Brute Force — Recursive Tiling + Trial-Division Primes
1Hint 1Explore hintHide hint
Stand at the left edge with w columns remaining. You can place a vertical brick (w−1 left) or, if w ≥ 4, a horizontal layer (w−4 left). Count both.
2Hint 2Explore hintHide hint
Base case: w = 0 is one complete tiling; w = 1, 2, 3 only allow vertical bricks, all reaching 1.
3Hint 3Explore hintHide hint
For the prime count, test each integer 2..M for primality by trial division up to its square root.
A · Core idea
Solve both halves the most literal way.
Tiling by recursion. Let f(w) count tilings of a 4×w wall. From the left edge you either stand one brick up (consume 1 column → f(w−1)) or, when w ≥ 4, lay a horizontal layer of four bricks (consume 4 columns → f(w−4)). So f(w) = f(w−1) + (w ≥ 4 ? f(w−4) : 0), with f(0) = 1 (empty wall is one valid tiling) and f(1) = f(2) = f(3) = 1.
Why the choices are exhaustive and non-overlapping. Look at the top-left cell: it's covered either by a vertical brick (forcing a full vertical brick in that column) or by the left end of a horizontal brick (which forces a full 4-column horizontal layer to keep the boundary flat). These two cases are mutually exclusive and cover every tiling exactly once — the hallmark of a clean counting recurrence.
Primes by trial division. For each integer v from 2 to M, check divisibility by every d up to √v; if none divide, v is prime. Count them.
Why we don't ship it. The recursion recomputes the same f(w) exponentially often (golden-ratio growth), and trial division is O(√v) per number. Both halves have cheap, well-known speed-ups: memoize/tabulate the recurrence to O(n), and replace trial division with a sieve at O(M log log M).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 5Interactive diagram
Tiling recursion tree
f(5)f(w) splits into f(w-1) and f(w-4); shared nodes recur — the memoization target.
2C · Code with teaching comments
Reference implementation previewpublic int redJohn(int n) { long m = tilings(n); return countPrimesTrial(m); } Explore the full codeHide the full code
D · Why it works and complexityO(φⁿ + M·√M) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Both stages are textbook-improvable: the tiling recurrence has only n distinct subproblems (cache them), and primality testing each number independently wastes the sharing a sieve exploits. The brute force exists to reveal the recurrence and the prime sub-task, not to run.
ComplexityO(φⁿ + M·√M) time, O(n) space — The tiling recursion branches up to twice per level → φⁿ-ish (golden-ratio-like) calls. Trial-division prime counting tests M numbers, each in O(√M) → O(M·√M).
E · Edge cases and pitfalls3Using f(w-2) (a 2×n board) instead of f(w-4) — wrong block size.Explore edge casesHide edge cases
Pitfalls
- Using f(w-2) (a 2×n board) instead of f(w-4) — wrong block size.
- Returning M instead of the prime count.
- Trial-dividing each number independently — slow versus a sieve.
Approach 2 of 3 · Optimal
Tabulated Tiling + Sieve of Eratosthenes (Optimal)
1Hint 1Explore hintHide hint
Fill f[0..n] iteratively: f[0..3] = 1, then f[i] = f[i-1] + f[i-4]. M = f[n].
2Hint 2Explore hintHide hint
Build a boolean sieve of size M+1, mark 0 and 1 non-prime, then for each prime p strike p*p, p*p+p, ... up to M.
3Hint 3Explore hintHide hint
Count the True entries — that's the number of primes ≤ M.
A · Core idea
Compute each stage with its standard efficient algorithm.
Stage 1 — tiling DP. Build the array bottom-up: f[0] = f[1] = f[2] = f[3] = 1, and for i ≥ 4, f[i] = f[i-1] + f[i-4]. Each value is computed once from already-filled predecessors, so the whole thing is O(n). Set M = f[n].
Stage 2 — sieve. To count primes ≤ M, allocate a boolean array isPrime[0..M], initialise all true, then set isPrime[0] = isPrime[1] = false. For each p from 2 while p·p ≤ M, if p is still marked prime, cross off every multiple starting at p·p (smaller multiples like 2p, 3p were already struck by smaller primes). Finally count the entries still true.
Why start crossing at p·p. Any composite q < p² has a prime factor smaller than p, so it was already eliminated when that smaller prime was processed. Starting at p² avoids redundant marking and is the standard sieve optimisation.
Why a sieve beats trial division here. Trial division pays O(√v) per number independently; the sieve shares work across all numbers, marking each composite a small number of times overall. For the M values arising from n ≤ 40, the sieve is effectively instant.
Edge handling. If M < 2 (i.e. M = 1 for small n), there are no primes ≤ M, so the answer is 0 — guard the sieve so you don't index a size-2 array incorrectly.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 7Array state
f[]
1,1,1,1,2,3,4,5 → M=5
3C · Code with teaching comments
D · Why it works and complexityO(n + M log log M) timeO(M) spaceOpen the invariant and proofExplore the proofHide the proof
The problem is two well-known algorithms wired in series: a Fibonacci-style tiling DP feeding its result as the upper bound of a Sieve of Eratosthenes. Seeing it as 'recurrence → sieve' is the whole solution; each piece is standard.
ComplexityO(n + M log log M) time, O(M) space — Tiling DP is a single O(n) pass. The Sieve of Eratosthenes marks composites in O(M log log M), then an O(M) scan counts primes.
E · Edge cases and pitfalls7n = 0 — f[0]=1 → M=1 → no primes ≤ 1 → 0.Explore edge casesHide edge cases
Edge cases handled
n = 0f[0]=1 → M=1 → no primes ≤ 1 → 0.n = 1M=1 → 0 (guarded by m < 2).n = 4M=2 → primes {2} → 1.n = 40M = f(40) (a few hundred thousand); sieve handles it instantly.
Pitfalls
- Forgetting the m < 2 guard — sieve loop/array sizing breaks for M=1.
- Letting p*p overflow int — cast to long before squaring.
- Using a +2 recurrence (2×n board) instead of +4.
Approach 3 of 3
Rolling 4-Variable Tiling — O(1) Space for Stage 1
1Hint 1Explore hintHide hint
f[i] only depends on f[i-1] and f[i-4]. Keep the last four values in a rolling window instead of the whole array.
2Hint 2Explore hintHide hint
Maintain a, b, c, d = f[i-4], f[i-3], f[i-2], f[i-1]; next = d + a; then shift the window.
3Hint 3Explore hintHide hint
The sieve stage is unchanged — it inherently needs O(M) space.
A · Core idea
Tighten the tiling recurrence's memory. Because f[i] reaches back at most 4 indices, you only need the last four values, not the full array.
Rolling window. Track a, b, c, d = f[i-4], f[i-3], f[i-2], f[i-1]. The next value is d + a (i.e. f[i-1] + f[i-4]). Then slide: a, b, c, d = b, c, d, next. After n − 3 slides starting from the four 1s, d holds f[n].
Why bother. For n ≤ 40 the array is trivially small, so this is mostly a demonstration of the bounded-look-back optimisation (the same idea that turns Fibonacci from O(n) to O(1) space). The dominant cost — and dominant memory — is the sieve, which fundamentally needs O(M).
Stage 2 unchanged. The prime count still uses the Sieve of Eratosthenes exactly as before; there's no O(1)-space way to count primes ≤ M that's competitive here.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 6Array state
start
(1,1,1,1)
2C · Code with teaching comments
Reference implementation previewpublic int redJohn(int n) { if (n < 4) return countPrimes(1); int a = 1, b = 1, c = 1, d = 1; // f[0..3] for (int i = 4; i <= n; i++) { int next = d + a;Explore the full codeHide the full code
D · Why it works and complexityO(n + M log log M) timeO(M) spaceOpen the invariant and proofExplore the proofHide the proof
A recurrence with a fixed look-back of 4 needs only 4 remembered values — the array is overkill. But composing with a sieve caps the overall space at O(M), so the rolling trick optimises only the cheap half. Knowing which stage dominates is the real takeaway.
ComplexityO(n + M log log M) time, O(M) space — Stage 1 becomes O(1) extra space by keeping four scalars; total time unchanged at O(n + M log log M), dominated by the sieve's O(M) memory.
E · Edge cases and pitfalls6n = 3 — n < 4 path → M=1 → 0 primes.Explore edge casesHide edge cases
Edge cases handled
n = 3n < 4 path → M=1 → 0 primes.n = 4One iteration → d=2 → primes {2} → 1.n = 0Handled by n < 4 → 0.
Pitfalls
- Shifting the window in the wrong order and corrupting f[i-4].
- Thinking O(1) space helps overall — the sieve still needs O(M).
- Skipping the n < 4 guard, then reading an uninitialised window.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int redJohn(int n) { int[] f = new int[Math.max(n + 1, 4)]; f[0] = f[1] = f[2] = f[3] = 1; for (int i = 4; i <= n; i++) { f[i] = f[i - 1] + f[i - 4];Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Wrong recurrence step
The wall is 4 tall and bricks are length 4, so a horizontal layer consumes 4 columns, not 2. Using +2 counts a different board.
Explore the code comparisonHide the code comparison
Wrong recurrence step
The wall is 4 tall and bricks are length 4, so a horizontal layer consumes 4 columns, not 2. Using +2 counts a different board.
Don't write this
f[i] = f[i - 1] + f[i - 2] # this is a 2xn boardWrite this instead
f[i] = f[i - 1] + f[i - 4] # 4xn wall2Returning M instead of the prime count
The problem asks for the number of primes ≤ M, not M. Stopping at M skips the entire second stage.
Explore the code comparisonHide the code comparison
Returning M instead of the prime count
The problem asks for the number of primes ≤ M, not M. Stopping at M skips the entire second stage.
Don't write this
return f[n]; // returns M, not the prime countWrite this instead
return countPrimes(f[n]);3Trial division instead of a sieve
Testing each number independently is O(M·√M); the Sieve of Eratosthenes shares work across numbers at O(M log log M).
Explore the code comparisonHide the code comparison
Trial division instead of a sieve
Testing each number independently is O(M·√M); the Sieve of Eratosthenes shares work across numbers at O(M log log M).
Don't write this
count = sum(1 for v in range(2, m + 1) if is_prime_trial(v))Write this instead
sieve = [True] * (m + 1)
# mark composites from p*p, then sum the True flagsRevise
Carry the pattern into the interview
Pattern to remember
Tiling recurrence (Fibonacci-like, step 1 or 4) followed by prime counting via sieve
Code pattern to memorize
# stage 1: tilings of a 4×n wall
f[0]=f[1]=f[2]=f[3]=1
for i in 4..n: f[i] = f[i-1] + f[i-4]
M = f[n]
# stage 2: count primes <= M
sieve = [True]*(M+1); sieve[0]=sieve[1]=False
for p in 2..sqrt(M):
if sieve[p]: mark multiples p*p..M
answer = count(sieve)Rules to remember
- 1Base cases span four values: f(0..3) = 1, because for widths 0–3 the only tiling is all-vertical bricks (you can't lay a horizontal 1×4 until you have 4 columns).
- 2The recurrence step is 1 or 4, not 1 or 2: a vertical brick consumes 1 column; a horizontal layer consumes 4 columns at once (four 1×4 bricks stacked).
- 3After computing M, the answer is the count of primes ≤ M, not M itself — don't forget the second stage.
- 4Seed the sieve with
sieve[0] = sieve[1] = false; 0 and 1 are not prime. - 5Mark composites starting at
p*p(smaller multiples already struck) and only sievepup to√M.
Use this pattern when
- Tiling / paving counts where each step covers a fixed block size → linear recurrence
- A problem chains a counting DP into a number-theoretic post-step (primes, divisors)
- Counting primes up to a bound → Sieve of Eratosthenes
- Fibonacci-family recurrences with a step larger than 1
Choose another pattern when
- Brick can be placed in two dimensions independently with overlaps → 2D profile DP, not a 1D recurrence
- You need the tilings themselves, not the count → backtracking enumeration
- M is astronomically large → can't sieve; need a prime-counting function (e.g. Meissel–Mertens)
- Block size varies per step → generalized recurrence, re-derive base cases
Interview takeaway
Recognise the wall-tiling count as a Fibonacci cousin with a step of 4 (vertical = −1 column, horizontal layer = −4 columns), then bolt on a sieve to count primes up to that value. Two classic subroutines composed — the trick is getting the four base cases and the +4 step right.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternA composition of two classics: a Fibonacci-family tiling recurrence (step 1 or 4, four base cases) feeding its result as the upper bound of a Sieve of Eratosthenes. Recognise tiling/paving counts as linear recurrences and chain number-theoretic post-steps with the appropriate standard algorithm.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Climbing StairsThe +1/+2 sibling — same linear recurrence with a smaller step and two base cases.
- Fibonacci ModifiedAnother recurrence-driven sequence problem, here with squaring and big integers.
- Count Primes (Sieve)Coming soonThe second stage in isolation — counting primes below a bound.
- Tiling a 2×n BoardComing soonThe classic domino tiling that yields f(n)=f(n−1)+f(n−2).