Количество "единичек"

[boomeer]

Вводится число n. Нужно определить сколько "единичек" в отрезке [1..n]
Например для 10 это 2, для 50 - 14.
Похоже на довольно стандартную задачу, но как сделать не пойму...

[caxap]

В лоб: перебрать все числа и посчитать единицы в каждом.

[boomeer]

Ограничение на время 2 секунды. N достигает 10^9

[worm2]

Ну тогда считать по отдельности в каждом разряде.
Попробуйте выявить закономерности.

[Maslov]

Сколько единичек в каждом полном десятке?
А сколько к ним добавляется в каждой полной сотне?