Let us subtract \(1\) from \(X\) to consider it as \(0\)-based. Additionally, since every string on the blackboard begins with \(1\), let us assume that it does not exist. (For instance, we see 1 as an empty string.)

Let us gradually determine the string in question from the top.

There are \(2^{(N-1)}\) strings that begin with \(0\) or are empty. Thus, if \(2^{(N-1)} \leq X\), the answer begins with \(1\). On the other hand, if \(1 \leq X < 2^{(N-1)}\), the answer begins with \(0\). If \(X=0\), the answer is an empty string.

If \(1 \leq X < 2^{(N-1)}\), the rest of the answer can be found by solving the same problem after letting \(N:=N-1\) and \(X:=X-1\). Similarly, if \(2^{(N-1)} \leq X\), the rest of the answer can be found by solving the same problem after letting \(N:=N-1\) and \(X:=X-2^{(N-1)}\).

A naive implementation of this would involve \(O(N)\) operations on integers with \(O(N)\) digits, for a total of \(O(N^2)\) time.

However, by maintaining \(X\) in binary, we can execute the operations in a total of \(O(N)\) time.

First, when checking whether \(2^k \leq X\), it is enough to see whether the \(k\)-th bit is \(1\), since \(x < 2^{k+1}\) always holds.

Next, when letting \(X:=X-1\), we can just calculate it as if doing it on paper until there is no more borrowing, when we break the loop. Doing this \(N\) times makes \(ceil(N/2^k)\) loops reach the \(k\)-th digit (\(ceil(x)\) is the smallest integer not less than \(x\)). This is because once borrowing happens up to the \(k\)-th bit, every digit below it becomes \(1\), so the next borrowing up to the \(k\)-th bit will happen \(2^k\) operations later.

Since \(\sum_{0 \leq k \leq N-1} ceil(N/2^k)\) is \(O(N)\), it shows that the total complexity is \(O(N)\).