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

[boomeer]

Вводится число n. Нужно определить сколько "единичек" в отрезке [1..n]
Например для 10 это 2, для 50 - 14.
Похоже на довольно стандартную задачу, но как сделать не пойму...
N может достигать 10^9
Пытался вывести формулу, но что то никак.
Можно динамикой предподсчитать сколько единичек от 1 до 10^k. Считаем сколько получилось на 10^(k-1), для 10^k очевидно ответ 10^(k-1)+то что было раньше(берется из соображения что мы можем после каждого числа поставить 0,1,2,3,4,5,6,7,8,9) Далее разбиваем свой отрезок от L до R на 2 части-от 1 до L и от 1 до R. Далее у нас сохраняется динамика, допустим у нас число L...равно 212344587. Берем и считаем ответ от 1 до 200000000, потом от 200000000 до 210000000 и тд

Под "единичками" имеется в виду числа, содержащие единички.

[Obey-Kun]

1. Делаешь функцию int numberOfOnes(int x), возвращающую кол-во единичек в числе x.
2. Прогоняешь цикл: for(;n>=1;--n){ sum_of_ones += numberOfOnes(n); }
3. ?????
4. PROFIT!

[NiCola999]

для 10 это 2, для 50 - 14.

что-то я не понял, можете привести пример

как понять от 1 до 10 2 единицы

[Obey-Kun]

1 ← 1 единица
2
3
4
5
6
7
8
9
10 ← 1 единица

от 1 до 10 две единицы.

[NiCola999]

понятно )

Делаешь функцию int numberOfOnes(int x), возвращающую кол-во единичек в числе x.

хехе, прикинь сколько цикл будет работать при n = 10^9
надо что-то похитрее...

кстати для 50 не 14, а 15

[Obey-Kun]

Тогда можно формулу вывести, ничего сложного по идее.

[Smitt&Wesson]

Задачка довольно простая.

1. берём число (для простоты от 0 до n)
2. делаем целочисленное деление командой div
3. во внутреннем цикле подсчитываем количество единиц в остатке
4. так повторяем до n = 0

Для числа 10^9 получим 9-ть внешних циклов и по 10 внутренних на какждую итерацию.
Итого 9*10=90 циклов!

[boomeer]

Сообщение от Obey-Kun

Тогда можно формулу вывести, ничего сложного по идее.

Пробовал я пробовал вывести формулу, доказать индукцией... И фиг

[NiCola999]

какие 90 итераций? считовод вотруба

внешний 10^9 итераций + внутренний от 1 до 9 итераций, сложность O(n)

[Smitt&Wesson]

Поспешил я с алгоритмом. С лёту не удаётся сделать .

Сообщение от NiCola999

какие 90 итераций? считовод вотруба

внешний 10^9 итераций + внутренний от 1 до 9 итераций, сложность O(n)

Но-но, полегче. Алгоритм верен отчасти. Решу - покажу.