Problema
Conta gli interi da left a right, inclusi gli estremi, che non hanno cifre adiacenti uguali. Usa la loro scrittura decimale usuale senza zeri iniziali. Lo zero e tutti gli altri numeri a una cifra sono validi.
Implementa counting_numbers(left, right).
Input
left: Il primo valore consentito.
right: L’ultimo valore consentito.
Output
Restituisci quanti valori soddisfano la regola.
Vincoli
0 ≤ left ≤ right ≤ 10¹⁸. L’intervallo può essere troppo grande per esaminare ogni intero singolarmente.
Esempi
Input:
left = 10
right = 15
Output atteso:
expected = 5Input:
long long left = 10;
long long right = 15;
Output atteso:
long long expected = 5;Input:
long left = 10;
long right = 15;
Output atteso:
long expected = 5;Spiegazione
Solo 11 ha cifre adiacenti uguali. Gli altri cinque numeri sono validi.
Input:
left = 0
right = 9
Output atteso:
expected = 10Input:
long long left = 0;
long long right = 9;
Output atteso:
long long expected = 10;Input:
long left = 0;
long right = 9;
Output atteso:
long expected = 10;Spiegazione
Tutti e dieci i valori hanno una sola cifra e quindi nessun vicino uguale.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Conta i numeri validi fino a ciascun estremo, poi sottrai per ottenere la risposta nell'intervallo.
Suggerimento 2
Il digit DP funziona perché la validità dipende da cifre adiacenti e dal fatto che il numero sia già iniziato.
Suggerimento 3
Gli zeri iniziali richiedono una gestione speciale per contare correttamente i numeri più corti.
Complessità attesa
tempo O(k * 10 * states), spazio aggiuntivo O(k * states)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.