Напишите метод, который будет подсчитывать количество цифр «2», используемых в записи чисел от 0 до n (включительно)

Как всегда, сначала мы попробуем решить задачу «в лоб».

Единственное интересное место в этом алгоритме — выделение numberOf2s в отдельный метод. Это делается для чистоты кода.

Улучшенное решение

Можно смотреть на задачу не с точки зрения диапазонов чисел, а с точки зрения разрядов — цифра за цифрой.

  0   1   2   3   4   5   6   7   8   9
 10  11  12  13  14  15  16  17  18  19
 20  21  22  23  24  25  26  27  28  29
...
110 111 112 113 114 115 116 117 118 119

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

Хотя тут стоит использовать слово «приблизительно», потому что необходимо учитывать граничные условия. Посчет количества двоек для диапазонов 1-100 и 1-37 будет различаться.

Точно количество двоек можно вычислить, рассмотрев все по отдельности разряды: digit < 2, digit = 2 и digit > 2.

Случай: digit < 2

Если x = 61523 и d = 3, то x[d] = 1 (это означает, что d-й разряд x равен 1). Рассмотрим двойки, находящиеся в 3-м разряде, в диапазонах 2000-2999, 12000-12999, 22000-22999, 32000-32999, 42000-42999 И 52000-52999. Мы не будем учитывать диапазон 62000-62999. В перечисленные диапазоны попадает 6000 двоек, находящихся в 3-м разряде. Такое же количество двоек можно получить, если подсчитать все двойки в 3-м разряде в диапазоне чисел от 1 до 6000.

Другими словами, чтобы рассчитать количество двоек в d-м разряде, достаточно округлить значение до 10d+1, а затем разделить на 10.

if x[d] < 2: count2sInRangeAtDigit(x, d) =
let y = round down до ближайшего
10d+1
return y / 10

Случай: digit > 2

Давайте рассмотрим случай, когда значение d-гo разряда больше, чем 2 (х[d] > 2). Если использовать ту же логику, становится понятно, что количество двоек в 3-м разряде диапазона 0-63525 будет таким же, как в диапазоне 0-7000. Таким образом, вместо округления вниз мы будем округлять вверх.

if x[d] > 2: count2sInRangeAtDigit(x, d) =
let y = round up до ближайшего
10d+1
return y / 10

Случай: digit = 2

Последний случай самый трудный, но мы можем использовать ту же логику. Пусть х = 62523 и d = 3. Мы знаем, что диапазоны не изменились (2000-2999, 12000-12999, ..., 52000-52999). Сколько двоек может появиться в 3-м разряде в диапазоне 62000-62523? Подсчитать несложно — 524 (62000, 62001, ..., 62523).
if x[d] > 2: count2sInRangeAtDigit(x, d) =
let y = округляем вниз до
10d+1
let z = правая сторона x (т.е. х % 10d)
return y / 10 + z + 1

Теперь нам нужно пройтись по каждой цифре в числе. Реализация данного кода относительно проста:

Данная задача требует тщательного тестирования. Убедитесь, что вы знаете все граничные случаи и проверили каждый из них.

Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.
Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».