Tous les défis
Difficile 1 résolu 100.0 % de réussite

Compter les nombres à voisins distincts

Comptez les valeurs d'une plage dont les chiffres décimaux adjacents ne sont jamais égaux.

Ce que vous allez apprendre

  • Compter les nombres jusqu'à une limite chiffre par chiffre
  • Suivre le chiffre précédent et la borne serrée
  • Répondre pour un intervalle avec f(b) - f(a - 1)

Problème

Comptez les entiers de left à right inclus, qui n'ont aucun chiffre voisin égal. Utilisez leur écriture décimale habituelle, sans zéros initiaux. Zéro et tous les autres nombres à un chiffre sont valides.

Implémentez counting_numbers(left, right).

Entrée

left : La première valeur autorisée.

right : La dernière valeur autorisée.

Sortie

Retournez combien de valeurs respectent la règle.

Contraintes

0 ≤ left ≤ right ≤ 10¹⁸. La plage peut être trop grande pour examiner chaque entier individuellement.

Exemples

Exemple 1
Entrée :
left = 10
right = 15

Sortie attendue :
expected = 5
Entrée :
long long left = 10;
long long right = 15;

Sortie attendue :
long long expected = 5;
Entrée :
long left = 10;
long right = 15;

Sortie attendue :
long expected = 5;

Explication

Seul 11 a des chiffres voisins égaux. Les cinq autres nombres sont valides.

Exemple 2
Entrée :
left = 0
right = 9

Sortie attendue :
expected = 10
Entrée :
long long left = 0;
long long right = 9;

Sortie attendue :
long long expected = 10;
Entrée :
long left = 0;
long right = 9;

Sortie attendue :
long expected = 10;

Explication

Les dix valeurs n'ont qu'un seul chiffre et donc aucun voisin égal.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Compte les nombres valides jusqu’à chaque borne, puis soustrais pour obtenir la réponse sur l’intervalle.

Indice 2

La digit DP convient bien, car la validité dépend des chiffres adjacents et du fait d’avoir commencé le nombre ou non.

Indice 3

Les zéros initiaux demandent un traitement spécial pour compter correctement les nombres plus courts.

Complexité attendue

temps O(k * 10 * states), espace supplémentaire O(k * states)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 807 ms - 5/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.