Alle Herausforderungen
Mittel 1 gelöst 100.0% Erfolgsquote

Ziffern subtrahieren, um Null zu erreichen

Verwende so wenige Ziffernsubtraktionen wie möglich, um Null zu erreichen.

Das lernst du

  • Einen Prozess als Zustände und Züge modellieren
  • Die minimale Schrittzahl bis 0 berechnen
  • DP mit einer gierigen Abkürzung vergleichen

Problem

Wähle in jedem Schritt eine aktuell im Zahlwert vorhandene, von Null verschiedene Dezimalziffer und subtrahiere diese Ziffer. Nach jedem Schritt werden die Ziffern aus dem neuen Wert entnommen. Finde die minimale Anzahl an Schritten, um Null zu erreichen.

Implementiere removing_digits(n).

Eingabe

n: Die positive Startzahl.

Ausgabe

Gib die geringste Anzahl an Subtraktionsschritten zurück.

Einschränkungen

1 ≤ n ≤ 1.000.000. Das Subtrahieren von Null ist kein zulässiger Zug und ausgeschlossen.

Beispiele

Beispiel 1
Eingabe:
n = 14

Erwartete Ausgabe:
expected = 3
Eingabe:
long long n = 14;

Erwartete Ausgabe:
long long expected = 3;
Eingabe:
long n = 14;

Erwartete Ausgabe:
long expected = 3;

Erläuterung

14 → 10 → 9 → 0 benötigt drei Schritte. Keine der möglichen ersten Subtraktionen erreicht Null in nur zwei Schritten.

Beispiel 2
Eingabe:
n = 7

Erwartete Ausgabe:
expected = 1
Eingabe:
long long n = 7;

Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long n = 7;

Erwartete Ausgabe:
long expected = 1;

Erläuterung

Subtrahiere die einzige Ziffer, 7, um sofort 0 zu erreichen.

So gehst du vor

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

Hinweis 1

Jede Zahl hängt von der besten Antwort für kleinere Zahlen ab, die durch das Entfernen einer Ziffer erreichbar sind.

Hinweis 2

Dynamic Programming über alle Werte bis n vermeidet doppelte Arbeit.

Hinweis 3

Denk daran, dass sich die verfügbaren Ziffern nach jeder Subtraktion ändern, und 0 ist nie eine gültige Wahl.

Erwartete Komplexität

Zeit O(n * d), zusätzlicher Speicher O(n)

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 942 ms - 2/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.