Alle Herausforderungen
Schwierig 1 gelöst 100.0% Erfolgsquote

Count Numbers With Distinct Neighbors

Count range values whose adjacent decimal digits are never equal.

Das lernst du

  • 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)

Problem

Übersetzung anzeigen

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.

Einschränkungen

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

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

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

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

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

So gehst du vor

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

Hinweis 1

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

Hinweis 2

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

Hinweis 3

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

Erwartete Komplexität

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

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.