Alle Herausforderungen
Schwierig 1 gelöst 100.0% Erfolgsquote

Zähle Zahlen mit unterschiedlichen Nachbarn

Zähle Werte im Bereich, deren benachbarte Dezimalziffern nie gleich sind.

Das lernst du

  • Zahlen bis zu einer Grenze Ziffer für Ziffer zählen
  • Die vorige Ziffer und die enge Grenze verfolgen
  • Einen Bereich als f(b) - f(a - 1) beantworten

Problem

Zähle alle Ganzzahlen von left bis right (beide einschließlich), bei denen keine benachbarten Ziffern gleich sind. Verwende dabei die übliche Dezimalschreibweise ohne führende Nullen. Die Null und alle anderen einstelligen Zahlen erfüllen die Bedingung.

Implementiere counting_numbers(left, right).

Eingabe

left: Der kleinste erlaubte Wert.

right: Der größte erlaubte Wert.

Ausgabe

Gib zurück, wie viele Werte die Bedingung erfüllen.

Einschränkungen

0 ≤ left ≤ right ≤ 10¹⁸. Der Bereich kann zu groß sein, um jede Zahl einzeln zu prüfen.

Beispiele

Beispiel 1
Eingabe:
left = 10
right = 15

Erwartete Ausgabe:
expected = 5
Eingabe:
long long left = 10;
long long right = 15;

Erwartete Ausgabe:
long long expected = 5;
Eingabe:
long left = 10;
long right = 15;

Erwartete Ausgabe:
long expected = 5;

Erläuterung

Nur 11 hat gleiche benachbarte Ziffern. Die anderen fünf Zahlen erfüllen die Bedingung.

Beispiel 2
Eingabe:
left = 0
right = 9

Erwartete Ausgabe:
expected = 10
Eingabe:
long long left = 0;
long long right = 9;

Erwartete Ausgabe:
long long expected = 10;
Eingabe:
long left = 0;
long right = 9;

Erwartete Ausgabe:
long expected = 10;

Erläuterung

Alle zehn Werte bestehen nur aus einer Ziffer und haben daher keine gleichen Nachbarn.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Zähle gültige Zahlen bis zu jedem Randwert und subtrahiere dann, um die Antwort für den Bereich zu erhalten.

Hinweis 2

Digit DP passt gut, weil die Gültigkeit von benachbarten Ziffern und davon abhängt, ob die Zahl schon begonnen hat.

Hinweis 3

Führende Nullen brauchen besondere Behandlung, damit kürzere Zahlen korrekt mitgezählt werden.

Erwartete Komplexität

Zeit O(k * 10 * states), zusätzlicher Speicher O(k * states)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 807 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.