すべてのチャレンジ
中級 1件解決済み 正答率100.0%

Subtract Digits to Reach Zero

Use as few digit subtractions as possible to reach zero.

このチャレンジで学べること

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

問題

翻訳を表示

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.

制約

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

例

例 1
入力:
n = 14

期待される出力:
expected = 3
入力:
long long n = 14;

期待される出力:
long long expected = 3;
入力:
long n = 14;

期待される出力:
long expected = 3;

解説

14 → 10 → 9 → 0 uses three steps. Neither possible first subtraction can reach zero in only two steps.

例 2
入力:
n = 7

期待される出力:
expected = 1
入力:
long long n = 7;

期待される出力:
long long expected = 1;
入力:
long n = 7;

期待される出力:
long expected = 1;

解説

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

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

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

ヒント 2

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

ヒント 3

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

目安の計算量

O(n * d) time, O(n) extra space

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

# コーダー 言語 時間 メモリ AI 評価 解答
1 ННикита Python 942 ms - 2/5 コードを見る

他の人の解答から学ぶ

コミュニティの解答

ネタバレ注意:下に1件の全解答あり まずは自分で挑戦してみましょう。他の開発者のコードやAIレビューも見ることができます。 サインインして課題を解くと議論に参加できます。