Как всегда, сначала мы попробуем решить задачу «в лоб».
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /* Подсчитываем число '2' между 0 и n */ int numberOf2sInRange(int n) { int count = 0; for (int i = 2; i <= n; i++) { // Можем начать с 2 count += numberOf2s(i); } return count; } /* подсчитываем число '2' в одном числе */ int numberOf2s(int n) { int count = 0; while (n > 0) { if (n % 10 == 2) { count++; } n = n / 10; } return count; } |
Единственное интересное место в этом алгоритме — выделение 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
Теперь нам нужно пройтись по каждой цифре в числе. Реализация данного кода относительно проста:
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 | public static int count2sInRangeAtDigit(int number, int d) { int powerOf10 = (int) Math.pow(10, d); int nextPowerOf10 = powerOf10 * 10; int right = number % powerOf10; int roundDown = number - number % nextPowerOf10; int roundUp = roundDown + nextPowerOf10; int digit = (number / powerOf10) % 10; if (digit < 2) { // если digit меньше 2 return roundDown / 10; } else if (digit == 2) { return roundDown / 10 + right + 1; } else { return roundUp / 10; } } public static int count2sInRange(int number) { int count = 0; int len = String.valueOf(number).length(); for (int digit = 0; digit < len; digit++) { count += count2sInRangeAtDigit(number, digit); } return count; } |
Данная задача требует тщательного тестирования. Убедитесь, что вы знаете все граничные случаи и проверили каждый из них.
Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.
Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».