Alle Herausforderungen
Mittel 1 gelöst 100.0% Erfolgsquote

Subtract Digits to Reach Zero

Use as few digit subtractions as possible to reach zero.

Das lernst du

  • Model a process as states and moves
  • Compute the minimum steps to zero
  • Compare DP with a greedy shortcut

Problem

Übersetzung anzeigen

At each step, choose a nonzero decimal digit currently present in the number and subtract that digit. Digits are taken from the new value after every step. Find the minimum number of steps needed to reach zero.

Implement removing_digits(n).

Input

n: The positive starting number.

Output

Return the fewest subtraction steps.

Einschränkungen

1 ≤ n ≤ 1,000,000. Subtracting zero is not a useful move and is excluded.

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 uses three steps. Neither possible first subtraction can reach zero in only two steps.

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

Subtract the only digit, 7, to reach 0 immediately.

So gehst du vor

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

Hinweis 1

Each number depends on the best answer for smaller numbers reachable by subtracting one digit.

Hinweis 2

Dynamic programming over all values up to n avoids repeated work.

Hinweis 3

Remember that the available digits change after every subtraction, and zero is never a valid choice.

Erwartete Komplexität

O(n * d) time, O(n) 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 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.