操作 \((x ,y)\) について、\(x \neq y\) であれば、操作は可逆で、逆操作はその操作そのものになります。そのため、文字列 \(T\) に対してある可逆な操作 \(i_1, i_2, \ldots, i_k\) を順に行って文字列 \(T'\) となるのであれば、\(T'\) に対して操作 \(i_k , \ldots i_2,, i_1\) を順に行うと \(T\) となります。

以下のような方法で操作列を前後から構成します。

• \(S\) に対して、できるだけ \(1\) を増やすように操作を行う。
• \(T\) の各 \(i\) について、 \(T_i = 0\) かつ \(S_i = 1\) であり、操作 \((i, i)\) が存在するのであれば、操作 \((i,i)\) を最後に行うことにし、\(T_i = 1\) とする。
• \(T\) に対して、できるだけ \(1\) を増やすように操作を行う。

この後、\(S = T\) となっていれば正しく変換が行われています。

操作の度に \(S\) あるいは \(T\) の \(1\) の個数が \(1\) 増えているため、操作回数は \(2N\) 以下になります。