समस्या
हर चरण में, संख्या में वर्तमान में मौजूद कोई भी गैर-शून्य दशमलव अंक चुनें और उस अंक को घटाएँ। हर चरण के बाद नए मान से अंक लिए जाते हैं। शून्य तक पहुँचने के लिए आवश्यक न्यूनतम चरणों की संख्या ज्ञात करें।
removing_digits(n) को लागू करें।
इनपुट
n: प्रारंभिक धनात्मक संख्या।
आउटपुट
सबसे कम घटाव चरणों की संख्या लौटाएँ।
सीमाएँ
1 ≤ n ≤ 1,000,000। शून्य घटाना कोई उपयोगी चाल नहीं है और इसे शामिल नहीं किया गया है।
उदाहरण
इनपुट:
n = 14
अपेक्षित आउटपुट:
expected = 3इनपुट:
long long n = 14;
अपेक्षित आउटपुट:
long long expected = 3;इनपुट:
long n = 14;
अपेक्षित आउटपुट:
long expected = 3;व्याख्या
14 → 10 → 9 → 0 में तीन चरण लगते हैं। किसी भी संभव पहले घटाव से केवल दो चरणों में शून्य तक नहीं पहुँचा जा सकता।
इनपुट:
n = 7
अपेक्षित आउटपुट:
expected = 1इनपुट:
long long n = 7;
अपेक्षित आउटपुट:
long long expected = 1;इनपुट:
long n = 7;
अपेक्षित आउटपुट:
long expected = 1;व्याख्या
केवल एक अंक, 7, को घटाकर तुरंत 0 तक पहुँच सकते हैं।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
हर number का answer उन smaller numbers के best answer पर depend करता है जो एक digit घटाकर मिलते हैं.
संकेत 2
n तक के सभी values पर dynamic programming करने से repeated work बचता है.
संकेत 3
याद रखो कि हर subtraction के बाद available digits बदल जाते हैं, और zero कभी valid choice नहीं है.
अपेक्षित जटिलता
समय O(n * d), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।