Dsa
Recursion
Hard
The Quantum Fractal Grid
A $2^N \times 2^N$ grid $M_n$ is constructed as follows. $M_0$ is a single cell containing 1. For $n > 0$, $M_n$ is divided into 4 quadrants of size $2^{n-1} \times 2^{n-1}$. Top-Left (Q1) is all 0s. Top-Right (Q2) is all 1s. Bottom-Left (Q3) is a copy of $M_{n-1}$. Bottom-Right (Q4) is an inverted copy of $M_{n-1}$ (0 becomes 1, 1 becomes 0). Given $N, R, C$, find the value at row $R$ and column $C$ (0-indexed). Constraints: $N \le 60$.
Key concepts
recursionmatrixspatial partitioning
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now