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

/* Подсчитываем число '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 в отдельный метод. Это делается для чистоты кода.

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

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

Мы знаем, что в последовательном ряду из десяти чисел последний разряд принимает значение 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-м разряде, достаточно округлить значение до 10^d+1, а затем разделить на 10.

if x[d] < 2: count2sInRangeAtDigit(x, d) =
let y = round down до ближайшего 10^d+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 до ближайшего 10^d+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 = округляем вниз до 10^d+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-компанию».}

Хинт для программистов: если зарегистрируетесь на соревнования Huawei Cup, то бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.

Перейти к регистрации