Subtract Digits to Reach Zero

Đề bài

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.

Ràng buộc

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

Ví dụ

Ví dụ 1

Đầu vào:
n = 14

Kết quả mong đợi:
expected = 3

Đầu vào:
long long n = 14;

Kết quả mong đợi:
long long expected = 3;

Đầu vào:
long n = 14;

Kết quả mong đợi:
long expected = 3;

Giải thích

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

Ví dụ 2

Đầu vào:
n = 7

Kết quả mong đợi:
expected = 1

Đầu vào:
long long n = 7;

Kết quả mong đợi:
long long expected = 1;

Đầu vào:
long n = 7;

Kết quả mong đợi:
long expected = 1;

Giải thích

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

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

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

Gợi ý 2

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

Gợi ý 3

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

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Removing Digits — 1637

Bạn sẽ học được gì

Đề bài

Input

Output

Ràng buộc

Ví dụ

Giải thích

Giải thích

Hướng tiếp cận

Tham khảo

Giải pháp cộng đồng