Question bank › Recursion
Dsa Recursion Hard

The Binary Dragon Coil

The 'Dragon Coil' sequence $S_n$ is defined recursively: $S_0 = "0"$. For $n > 0$, $S_n = S_{n-1} + "1" + \text{reverse}(\text{flip}(S_{n-1}))$, where 'flip' changes '0' to '1' and '1' to '0'. For example, $S_1 = "011"$ and $S_2 = "0111001"$. Given $N$ and $K$, find the $K$-th character (0-indexed) of $S_N$. Constraints: $N \le 60$, $K < 2^{N+1}-1$.

Key concepts

recursionsequencedivide and conquer

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
Part of InterviewLab's verified interview question bank. We show the prompt and concepts to practise with — never a copy-paste solution.