Как всегда, сначала мы попробуем решить задачу «в лоб».
/* Подсчитываем число '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
Теперь нам нужно пройтись по каждой цифре в числе. Реализация данного кода относительно проста:
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-компанию».