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

[Obey-Kun]

Попробуйте это:

можно находить позицию самой левой единицы в числе и пропускать соответствующее число чисел, нарастив счётчик на их количество.

Так время сократится.

[Акоб]

Мне кажется, что я знаю как можно построить вычисление достаточно быстро. но нечестно!
достаточно посчитать, сколько чисел в диапазонах десяток, сотен, тысяч и т.д. т.е. 10^I
сохранить эти значения, а потом использовать их в вычислениях. вроде бы там получается не очень сложно...

я именно на эту тему и думаю.Еще хочу понять, как можно раздробить цыфру.
скажите мне пожалуйста сколько будет для
10000
100000
1000000
10000000
100000000
1000000000

[Obey-Kun]

выше давали решение в лоб, посчитай

[Акоб]

он у меня не компелируется.

[Obey-Kun]

Вот это не компилируется?

#include <iostream>

inline bool valueContainsOne(int n)
{
    do {
        if (n % 10 == 1) {
            return true;
        }
    } while (n /= 10);
    return false;
}

int main()
{
    int x;
    do {
        std::cout << "Enter fucking positive number: ";
        std::cin >> x;
    } while (x < 1);
    int result = 0;
    for (; x >= 1; --x) {
        if (valueContainsOne(x)) {
            ++result;
        }
    }
    std::cout << "Your answer is " << result << ", dumbass." << std::endl;
}

[Serge_Bliznykov]

N= 10 комбинаций : 2
N= 100 комбинаций : 20
N= 1000 комбинаций : 272
N= 10000 комбинаций : 3440
N= 100000 комбинаций : 40952
N= 1000000 комбинаций : 468560
N= 10000000 комбинаций : 5217032
N= 100000000 комбинаций : 56953280
N= 1000000000 комбинаций : 612579512

[boomeer]

Я нашел окончательный алгоритм! =) "Без пробелов"

[Serge_Bliznykov]

Я нашел окончательный алгоритм! =) "Без пробелов"

я в Вас верил!
ну-ка, делитесь!
(пока я вижу решение только на основании Вашей предыдущей формулы) + проверка, если в исходном числе есть 1-ца - то вызываем рекуренто данную формулу с тем "остатком", который идёт после единицы...

Расскажите, к чему Вы пришли.

ну, и если это не секрет и сильно Вас не затруднит - расскажите, как Вы вообще сумели вывести формулу?!!

[boomeer]

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

я в Вас верил!
ну-ка, делитесь!
(пока я вижу решение только на основании Вашей предыдущей формулы) + проверка, если в исходном числе есть 1-ца - то вызываем рекуренто данную формулу с тем "остатком", который идёт после единицы...

Расскажите, к чему Вы пришли.

ну, и если это не секрет и сильно Вас не затруднит - расскажите, как Вы вообще сумели вывести формулу?!!

Итак. Окончательная формула такова: Пробегаемся по разрядам числа. Если число больше 1 то вычитаем из него 1 и умножаем это число на 9^разряд числа. Так бежим либо до конца, либо пока не встретим единичку. Встретили - значит это последнее число. Складываем все эти цифры. Теперь из n+1 вычитаем эту сумму. Все.

Относительно последней цифры: Если были цифры 1 до сих пор, мы включаем последнюю цифру, и добавляем 1, если это 0. Таким образом добавляем 4 для 5394, 1 для 5390, ничего для 5216,но добавляем 1 для 5391.

Пусть n=31874, тогда 2*9^4+1*9^3=13851, 31874+1-13851=18024
Это подтверждает решение в лоб

А как вывел... начал считать что 1 это все кроме 0,2...9. Так начал отнимать 1. Потом перешел в 9тиричную систему... Как то так. (может бред, но работает! =) )

[NiCola999]

попробуйте сделать тест от 1 до 10^9, решение в лоб vs ваш алгоритм. Что-то мне не оч верится в правильность вашего =)