Задача с вычислением целых чисел

Условие задачи: необходимо определить количество целых чисел из ряда от 1 до 1000, которые содержат цифры 3. При этом, если количество троек больше одной, как в числе 333, то учет всех цифр не производится, число записывается всего 1 раз. Суть вопроса, сколько чисел содержит как минимум одну цифру 3 из предложенного диапазона.

Решение задачи

Начнем с наибольшего количества идущих подряд троек – это диапазон от 300 до 399, где каждое число не зависимо от десятых имеет 3. Так сразу насчитываем 100 чисел.

Существует еще одна сотня, где тройка стоит на втором месте, к примеру 30-39, 130-139, 230-239 и так вплоть до 930-939. Так как ранее мы уже учли весь диапазон от 300 до 399, то 10 чисел из ряда следует вычесть, чтобы дважды их не посчитать. Таким образом у нас получилось 100 + 90 = 190 чисел.

Теперь нужно рассчитать количество окончаний на 3, то есть ряд значений 3, 13, 23, 33 и т.д. По аналогии с предыдущими случаями, таких чисел всего будет 100 штук, но нужно вычесть диапазон (303…393), то есть придется отнять 10 чисел. Сейчас получилось ещё 90 штук, но в подборке с периодичностью в 10 значений будут попадаться учтенные цифры (133, 233, 433…). Необходимо снова вычесть 9 таких чисел из 90, так получаем 81. Осталось всего лишь добавить все полученные значения.

Количество чисел 3 в диапазоне от 1 до 1000 составляет: 100 + 90 + 81 = 271.

Как посчитать быстрее?

Действительно, есть способ справиться существенно быстрее, то есть рассчитать все десятичные числа за исключением 3. Определить количество записей, не содержащих 3 можно просто перемножив все остальные числа 9 * 9 * 9 = 729. Соответственно осталось только отнять от всего количества полученный результат 1000-729 = 271.

Отметим, что таким же образом можно посчитать наличие любого числа от 1 до 9, кроме 0, так как оно не может стоять первым. Немного подправив формулу получается 100 чисел 0 в десятых и 90 в сотых (общее количество - 100, но минус 10 учтенных). То есть 0 встречается всего 190 раз.