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

[Smitt&Wesson]

Тут наблюдается определённая закономерность с единицей в старшем разряде (пока не пойму какая).

0-9 = 1
10-99 = 19
(100-119) = 32 + (120-199) = 16
200-999 = 20 * 8 (8 диапазонов).

заметно, что 1-а (или её отсутствие) в старшем разряде сильно влияет на цикличность суммы.
Дальше пока не разобрался.

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

имелось в виду, что из 15 надо сделать strin 151413121110987654321 и посчитать кол-вол единиц, но это не вариант, ибо как оказалось, надо не единицы считать, а числа с как минимум одной единицей

Ваш способ верен, в числе 15 действительно 8 единичек, но для числа 10^9, никакой оперативки не хватит. Имеется ввиду применение вычислительных методов.
Можно поступить так.
Каждое число переводить в string и подсчитывать 1-и, но для числа 10^9, это будет очень долгий процесс.

[Акоб]

можно написать генератор 
for(int i = 0; i <=9; i++)
    {
      if(i == 1)
         n++; 
    for(int j = 0; j <= 9; j++)
       {
           if(j == 1)
              n++;     
        for(int k = 0; k <= 9; k++)
            {
               if(k == 1)
                  n++;  
            for(int c = 0;c <= 9; c++)
                 {
                   if(c == 1)
                      n++;
                    if(i*1000 +j*100 +k*10 + c == N)
                      {
                          cout<<n<<endl;  
                         return 0;
                      }        
                 }
             }
        }
     }

[Smitt&Wesson]

Сообщение от Акоб

можно написать генератор

Можно и так, но для числа 10^9, придётся писать 10 вложенных циклов. Вы часом не из Индии .

[Акоб]

написть цикл каторый я предложил для 10^4 и найти алгоритм.
нет не из Идии
из Армении
где сам автор?

[Smitt&Wesson]

Сообщение от Акоб

написть цикл каторый я предложил для 10^4 и найти алгоритм.
нет не из Идии
из Армении
где сам автор?

Ну, до 1000, я и так разобрался. Весь вопрос в общем алгоритме. И доказательстве его правильности для любого, произвольно взятого, диапазона чисел.
Автор пропал куда-то. Испугался собственной темы .

[NiCola999]

Вы часом не из Индии

.

[Акоб]

и до чего же дошел?

[boomeer]

Сообщение от Smitt&Wesson

Ну, до 1000, я и так разобрался. Весь вопрос в общем алгоритме. И доказательстве его правильности для любого, произвольно взятого, диапазона чисел.
Автор пропал куда-то. Испугался собственной темы .

Тут я. Но последний раз за сегодня =)
Придумал такое решение.
От каждой цифры числа, кроме числа единиц, которая больше 1 отнимаем 1. Умножаем это число на 9. Складываем все + число единиц числа. Теперь от n+1 отнимем это число. Вуаля.
n=29 таким образом 1*9 + 9 = 18. Вычтите из n+1, и получаем 12
5394=9*9*9*4+2*9*9+8*9+4=5395-3154=2241
для 100: 1*9*9=81; 101-81=20
Писал сумбурно, если что завтра поясню как решал)

[Obey-Kun]

Вот в лоб. У меня для 1234512345 оно 45 секунд считает.

#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;
}

Можно распараллелить по процессорам при помощи OpenMP (+ 3 строчки к исходникам) или считать средствами видеокарты :D.

[NiCola999]

да нет в лоб хреново будет, но всё-таки: =))

#include <stdio.h>

int isOnes(int n){
    for(;n > 0; n/=10){
            if(n%10 == 1) return 1;
    }
    return 0;
}

int main(void){
    
    int i, sum = 0;
    for(i=1; i<=1000000000; i++) sum += isOnes(i);
    printf("%d\n", sum);
    return 0;
}

612579512

real	1m3.078s
user	0m57.632s
sys	0m1.508s