Задача заставила подумать.
Как уже описано на форуме,  нужно научиться считать количество единиц, которые встречаются в числах от 1 до X и подбирать X бинарным поиском.

И вот мне этот подсчет долго не давался.

Итог такой.

Считать можно рекурсивно.
Для этого нужно воспользоваться тем,  что для чисел вида X=999...999 искомое количество единиц равно (log10(X)+1) *10^log10(X).
Этот факт я заметил эксперимнтально.

То есть я имею в виду
count_ones (99)=20
count_ones (999)=300
count_ones (9999)=4000
и так далее.

Отсюда и вытекает способ .

Вычисляем сначала для X с зануленными разрядами кроме самого главного,  затем прибавляем значение функции от X с зануленным главным разрядом .

Я приведу пример для небольшого числа.

Пусть X=666.

Тогда посчитаем отдельно для 0-99, умножим на 6,  прибавим к ответу; затем отдельно для 100-200, прибавим это к ответу , затем рекурсивно для 600-666 то есть просто для 0-66.

http://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/

В сущности та же задача,  только считаем сумму единиц.