The answer is the sum of the following:

• the number of integers between \(1\) and \(N\) that begin with \(1\)
• the number of integers between \(1\) and \(N\) that begin with \(11\)
• the number of integers between \(1\) and \(N\) that begin with \(111\)
• \(\vdots\)

This is because an integer \(x\) with \(k\) leading ones is contained in the first \(k\) of the lists above.

Now, what kinds of integers begin with \(111\), for instance? We can see that those numbers are in the following ranges:

• \([111, 112)\)
• \([1110, 1120)\)
• \([11100, 11200)\)
• \(\vdots\)

Generally, we are interested in the ranges of the form \([1\cdots 10\cdots 0, 1\cdots 20\cdots 0)\).

Now, we just need to count the numbers at most \(N\) in those ranges.

We only need to consider \(O(\log^2N)\) ranges of the form \([1\cdots 10\cdots 0, 1\cdots 20\cdots 0)\), so the time complexity will also be \(O(\log^2N)\).