Найти количество нулей в записи чисел от 1 до n

#алгоритм #математика

Дано натуральное число n. Требуется найти кол-во цифр '0', встретившихся в записи
чисел от 1 до n, n <= 10^16. Очевидно, тривиальный алгоритм будет работать долго.    

Ответы

Ответ 1

Как и для большинства олимпиадных задач, для этой нашлось довольно короткое и быстрое
решение. Решил ее так: рассматривал заданное число N по цифрам от младших разрядов
к старшим. На каждом шаге имеются:

цифра в текущем разряде
число - младшие разряды (все что справа от текущей позиции)
число - старшие разряды (все что слева от текущей позиции)

1) Для первого разряда верно утверждение, что 0 там будет встречаться ровно такое
число раз, которое осталось в старших разрядах. Т.е. для числа 234, 0 в разрядах единиц
будет встречаться 23 раза, для 105 - 10 раз и т.д.
2) Для остальных разрядов (десятки, сотни, тысячи и т.д.) нужно рассмотреть два случая
- когда цифра больше нуля и когда она равна нулю:


Когда цифра в разряде больше нуля, то логика практически такая же как и для первого
разряда: На этой позиции 0 будет встречаться ровно такое число раз, которое осталось
в старших разрядах, но умноженное на 10 в степени текущего разряда. Поясню на примере:
число 123. На позиции двойки 0 будет встречаться 1 * 10 = 10 раз - для чисел 100 -
109. Или, число 2308: на позиции тройки 0 будет встречаться 2 * 100 = 200 раз. Это
числа 1000-1099 и 2000-2099.


Когда цифра в разряде равна нулю, то НЕВЕРНО утверждать, что 0 в ней встретиться
столько раз, сколько было в предыдущем случае (когда цифра не равна нулю). Сейчас он
там встретится меньшее число раз. Опять сразу перейду к примеру: число 201. сколько
раз 0 будет стоять в разряде десятков? Ответ - 12. Это числа 100-109, 200 и 201. Так
как же получить это число?.. Для этого нужно из числа в старших разрядах вычесть единицу,
умножить его на 10 в степени текущего разряда и прибавить к этому произведению число
в младших разрядах. И еще добавить единицу. Т.е. для приведенного выше числа 201 это
будет 1 * 10 + 1 + 1 = 12. Дополнительная единица нужна, чтобы не потерять число, когда
младшие разряды равно нулю, это 200 в данном случае. (Долго шел к этому пункту, и извиняюсь
за невнятное объяснение. Кому будет проще, то это действие у меня вызывает аналогию
с вычитанием в столбик, когда вычитаемое содержит нули)


Ну и собственно, реализация алгоритма:
int rank = 1;   // Номер разряда (начинаем с младших)
long res = 0;   // Результат
long high = N;  // Число в старших разрядах (изначально равно N)
long low = 0;   // Число в младших разрядах (изначально равно 0)

while (high > 0)
{
    long digit = high % 10;  // Текущая цифра
    high = high / 10;        // Уменьшаем число в старших разрядах

    if (rank > 1 && digit == 0)
    {
        res += ((high - 1) * rank) + (low + 1);  // Случай 2.2
    }
    else
    {
         res += high * rank;  // Случаи 1 и 2.1
    }

    low += rank * digit;  // Увеличиваем число в младших разрядах
    rank *= 10;           // Переходим к следующему разряду
}

// output res