Посчитайте целые числа от left до right включительно, у которых нет одинаковых соседних цифр. Используйте их обычную десятичную запись без ведущих нулей. Ноль и все остальные однозначные числа подходят под условие.
Реализуйте функцию counting_numbers(left, right).
Ввод
left: Первое допустимое значение.
right: Последнее допустимое значение.
Вывод
Верните количество значений, удовлетворяющих правилу.
Ограничения
0 ≤ left ≤ right ≤ 10¹⁸. Диапазон может быть слишком большим, чтобы проверять каждое число по отдельности.
Примеры
Ввод:
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;Пояснение
Только 11 имеет одинаковые соседние цифры. Остальные пять чисел подходят.
Ввод:
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;Пояснение
Все десять значений состоят из одной цифры и, следовательно, не имеют одинаковых соседей.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Считайте подходящие числа до каждого конца отрезка, затем вычитайте и получите ответ для диапазона.
Подсказка 2
Подходит digit DP, потому что допустимость зависит от соседних цифр и от того, начали ли вы число.
Подсказка 3
Нули в начале требуют отдельной обработки, чтобы более короткие числа считались правильно.
Ожидаемая сложность
O(k * 10 * states) по времени, O(k * states) доп. памяти
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.