Подсчитайте числа, не содержащие 3

Для числа n напишите функцию, которая возвращает количество чисел от 1 до n, не содержащих цифры 3 в их десятичном представлении.
Примеры:

 Ввод: n = 10
Выход: 9 

Исходные данные: n = 45
Выход: 31 
// Числа 3, 13, 23, 30, 31, 32, 33, 34, 
// 35, 36, 37, 38, 39, 43 содержат цифру 3. 

Ввод: n = 578.
Выход: 385

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

Решение:
Мы можем решить это рекурсивно. Пусть count (n) будет функцией, которая считает такие числа.

 'msd' -> самая значимая цифра в n 
'd' -> количество цифр в n.

count (n) = n, если n <3

count (n) = n - 1, если 3 <= n 10 и msd не равно 3

count (n) = count (msd * (10 ^ (d-1)) - 1) 
           если n> 10 и msd равно 3

Разберемся с решением с n = 578. 
count (578) = 4 * count (99) + 4 + count (78)
Средний член 4 добавлен, чтобы включить числа 
100, 200, 400 и 500.

В качестве другого примера возьмем n = 35.  
count (35) = count (3 * 10-1) = count (29)

Выход:

 385

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .