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

Count Numbers With Distinct Neighbors

Count range values whose adjacent decimal digits are never equal.

Ce que vous allez apprendre

  • Count numbers up to a limit digit by digit
  • Track the previous digit and tight bounds
  • Answer a range as f(b) - f(a - 1)

Problème

Afficher la traduction

Count integers from left through right, including both endpoints, that have no equal neighboring digits. Use their usual decimal writing with no leading zeroes. Zero and all other single-digit numbers qualify.

Implement counting_numbers(left, right).

Input

left: The first allowed value.

right: The last allowed value.

Output

Return how many values satisfy the rule.

Contraintes

0 ≤ left ≤ right ≤ 10¹⁸. The range may be too large to inspect each integer individually.

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

Only 11 has equal neighboring digits. The other five numbers qualify.

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

All ten values have just one digit and therefore no equal neighbors.

Comment l'aborder

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

Indice 1

Count valid numbers up to each endpoint, then subtract to get the range answer.

Indice 2

Digit DP fits because validity depends on adjacent digits and whether you have started the number.

Indice 3

Leading zeros need special handling so that shorter numbers are counted correctly.

Complexité attendue

O(k * 10 * states) time, O(k * states) extra space

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.