@0x10

А давайте все комбинаторные задачи решать на GPU в 100500 потоков?)

В данном конкретном случае нас интересует только количество знаков в числе n.
Рассматриваем числа, состоящие из 1 знака. Сколько их может быть? Вместе с нулем - 10. Сколько может встретиться двоек? Одна. Тут все как будто бы просто.

Далее. Рассмотрим двузначные числа вида AB. В данном случае A может принять 9 значений, B - 10. Т.е. всего чисел 90. Но в этих числах присутствует двойка. А сколько чисел без двойки? Тогда для A остается 8 вариантов, для B - 9. Всего чисел без двоек - 72. Очевидно, что с двойками - 90 - 72 = 18.

Таким образом можно просчитать для всех k-значных чисел, а в конце сложить результаты.

Добавлено через 5 минут
Нюанс: такой подход не учитывает кривой верхней границы. Т.е. сработает для диапазона [0, 999], но выдаст ерунду для [0, 500]. И все-таки придерживаюсь мнения, что такие вещи решаются не перебором) Но думать уже влом, поэтому отправляюсь спать.

Вернуться к обсуждению:
Подсчитывать количество цифр 2 C++

1