Все задачи
Сложно Решена: 1 Процент решений: 100.0%

Count Numbers With Distinct Neighbors

Count range values whose adjacent decimal digits are never equal.

Чему вы научитесь

  • Count numbers up to a limit digit by digit
  • Track the previous digit and tight bounds
  • Answer a range as f(b) - f(a - 1)

Условие

Показать перевод

Count integers from left through right, including both endpoints, that have no equal neighboring digits. Use their usual decimal writing with no leading zeroes. Zero and all other single-digit numbers qualify.

Implement counting_numbers(left, right).

Input

left: The first allowed value.

right: The last allowed value.

Output

Return how many values satisfy the rule.

Ограничения

0 ≤ left ≤ right ≤ 10¹⁸. The range may be too large to inspect each integer individually.

Примеры

Пример 1
Ввод:
left = 10
right = 15

Ожидаемый вывод:
expected = 5
Ввод:
long long left = 10;
long long right = 15;

Ожидаемый вывод:
long long expected = 5;
Ввод:
long left = 10;
long right = 15;

Ожидаемый вывод:
long expected = 5;

Пояснение

Only 11 has equal neighboring digits. The other five numbers qualify.

Пример 2
Ввод:
left = 0
right = 9

Ожидаемый вывод:
expected = 10
Ввод:
long long left = 0;
long long right = 9;

Ожидаемый вывод:
long long expected = 10;
Ввод:
long left = 0;
long right = 9;

Ожидаемый вывод:
long expected = 10;

Пояснение

All ten values have just one digit and therefore no equal neighbors.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Count valid numbers up to each endpoint, then subtract to get the range answer.

Подсказка 2

Digit DP fits because validity depends on adjacent digits and whether you have started the number.

Подсказка 3

Leading zeros need special handling so that shorter numbers are counted correctly.

Ожидаемая сложность

O(k * 10 * states) time, O(k * states) extra space

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

# Участник Язык Время Память Оценка ИИ Решение
1 ННикита Python 807 ms - 5/5 Посмотреть код

Учитесь у других

Решения сообщества

Внимание, спойлер: ниже 1 полное решение Попробуйте сначала решить сами. Вы всегда можете посмотреть код других и AI-обзоры. Войдите и решите задание, чтобы присоединиться к обсуждению.