Problema
Conte os inteiros de left até right, incluindo ambos os extremos, que não possuem dígitos vizinhos iguais. Considere a escrita decimal usual, sem zeros à esquerda. Zero e todos os outros números de um dígito são válidos.
Implemente counting_numbers(left, right).
Entrada
left: O primeiro valor permitido.
right: O último valor permitido.
Saída
Retorne quantos valores satisfazem a regra.
Restrições
0 ≤ left ≤ right ≤ 10¹⁸. O intervalo pode ser grande demais para inspecionar cada inteiro individualmente.
Exemplos
Entrada:
left = 10
right = 15
Saída esperada:
expected = 5Entrada:
long long left = 10;
long long right = 15;
Saída esperada:
long long expected = 5;Entrada:
long left = 10;
long right = 15;
Saída esperada:
long expected = 5;Explicação
Apenas o 11 possui dígitos vizinhos iguais. Os outros cinco números são válidos.
Entrada:
left = 0
right = 9
Saída esperada:
expected = 10Entrada:
long long left = 0;
long long right = 9;
Saída esperada:
long long expected = 10;Entrada:
long left = 0;
long right = 9;
Saída esperada:
long expected = 10;Explicação
Todos os dez valores têm apenas um dígito e, portanto, não possuem vizinhos iguais.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Conte os números válidos até cada extremo e depois subtraia para obter a resposta do intervalo.
Dica 2
Digit DP funciona bem porque a validade depende de dígitos adjacentes e de já termos começado o número.
Dica 3
Zeros à esquerda precisam de tratamento especial para que números menores sejam contados corretamente.
Complexidade esperada
tempo O(k * 10 * states), espaço extra O(k * states)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.