Подсчёт появлений цифры 1 в диапазоне от 0 до N

Условие

Вам дано целое число N. Нужно вычислить, сколько раз цифра 1 встречается в записи всех целых чисел от 0 до N включительно.

Ответ

Считайте вклад каждой десятичной позиции отдельно по старшей части, текущей цифре и младшей части N. Это позволяет избежать перебора всех чисел от 0 до N.

Вариант для неотрицательного int N:

static long countOnes(int n) {
    if (n < 0) throw new IllegalArgumentException();
    long count = 0;
    for (long factor = 1; factor <= n; factor *= 10) {
        long higher = n / (factor * 10);
        long digit = (n / factor) % 10;
        long lower = n % factor;
        count += higher * factor;
        if (digit == 1) count += lower + 1;
        else if (digit > 1) count += factor;
    }
    return count;
}

Например, для N=13 ответ 6: 1, 10, две единицы в 11, 12 и 13. Время O(log N), память O(1). Long нужен для счётчика и промежуточных произведений; для диапазона long потребуется дополнительная защита переполнения.