Problema
Cuenta los enteros desde left hasta right, incluyendo ambos extremos, que no tengan dígitos vecinos iguales. Usa su escritura decimal habitual, sin ceros a la izquierda. El cero y todos los demás números de un solo dígito califican.
Implementa counting_numbers(left, right).
Entrada
left: El primer valor permitido.
right: El último valor permitido.
Salida
Devuelve cuántos valores cumplen la regla.
Restricciones
0 ≤ left ≤ right ≤ 10¹⁸. El rango puede ser demasiado grande para inspeccionar cada entero individualmente.
Ejemplos
Entrada:
left = 10
right = 15
Salida esperada:
expected = 5Entrada:
long long left = 10;
long long right = 15;
Salida esperada:
long long expected = 5;Entrada:
long left = 10;
long right = 15;
Salida esperada:
long expected = 5;Explicación
Solo el 11 tiene dígitos vecinos iguales. Los otros cinco números califican.
Entrada:
left = 0
right = 9
Salida esperada:
expected = 10Entrada:
long long left = 0;
long long right = 9;
Salida esperada:
long long expected = 10;Entrada:
long left = 0;
long right = 9;
Salida esperada:
long expected = 10;Explicación
Todos los diez valores tienen solo un dígito y por lo tanto no tienen vecinos iguales.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Cuenta los números válidos hasta cada extremo y luego resta para obtener la respuesta del rango.
Pista 2
Digit DP encaja porque la validez depende de dígitos adyacentes y de si ya has empezado el número.
Pista 3
Los ceros a la izquierda necesitan tratamiento especial para contar bien los números más cortos.
Complejidad esperada
tiempo O(k * 10 * states), espacio extra O(k * states)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.