\(X\) から \(1\) を引いて \(0\)-based index で考えることにします． また，黒板に書かれた文字列はすべて \(1\) から始まるので，これをないものとして考えることにします．（例えば本来 1 だったものは空文字列と考えます．）

答えとなる文字列を先頭から定めていくことにします．

空文字列，もしくは \(0\) から始まる文字列は \(2^{(N-1)}\) 個存在します． よって，\(2^{(N-1)} \leq X\) である場合，答えの先頭は \(1\) です． 逆に，\(1 \leq X < 2^{(N-1)}\) のとき，答えの先頭は \(0\) です． \(X=0\) の時は答えは空文字列です．

\(1 \leq X < 2^{(N-1)}\) の時，答えの残りの部分は，\(N:=N-1\)，\(X:=X-1\) として同じ問題を解けば求められます． 同様に，\(2^{(N-1)} \leq X\) の時，答えの残りの部分は，\(N:=N-1\)，\(X:=X-2^{(N-1)}\) として同じ問題を解けば求められます．

これを愚直に実装すると，\(O(N)\) 桁の整数に対する演算が \(O(N)\) 回あるので，全体で \(O(N^2)\) 時間になってしまいます．

しかし，\(X\) を \(2\) 進表記で管理しておくと，すべての演算を合計で \(O(N)\) 時間で実行できます．

まず，\(2^k \leq X\) であるかどうかを確認するとき，必ず \(x < 2^{k+1}\) であることから，単に \(k\) 桁目が \(1\) であるかどうかを見ればよいです．

次に，\(X:=X-1\) とするときは，素直に下の桁から筆算を行い，繰り下がりがなくなったら途中で break すればよいです． この操作を \(N\) 回行ったとき，\(k\) 桁目までループが回る回数は \(ceil(N/2^k)\) です（\(ceil(x)\) は \(x\) 以上の最小の整数）． 何故なら，一度 \(k\) 桁目まで繰り下がりが起きたとすると，それより下の桁はすべて \(1\) になっているため，もう一度 \(k\) 桁目まで繰り下がるためには \(2^k\) 回の操作が必要だからです．

\(\sum_{0 \leq k \leq N-1} ceil(N/2^k)\) は \(O(N)\) なので，これで計算量が全体で \(O(N)\) であることが証明できました．