650। 2 कुंजी कीबोर्ड

कठिनाई: मध्यम

विषय: गणित, गतिशील प्रोग्रामिंग

नोटपैड की स्क्रीन पर केवल एक अक्षर 'ए' होता है। आप प्रत्येक चरण के लिए इस नोटपैड पर दो में से एक ऑपरेशन कर सकते हैं:

• सभी को कॉपी करें: आप स्क्रीन पर मौजूद सभी पात्रों को कॉपी कर सकते हैं (आंशिक प्रतिलिपि की अनुमति नहीं है)।
• चिपकाएं: आप पिछली बार कॉपी किए गए अक्षरों को चिपका सकते हैं।

एक पूर्णांक n दिया गया है, स्क्रीन पर वर्ण 'ए' को ठीक n बार प्राप्त करने के लिए ऑपरेशन की न्यूनतम संख्या लौटाएं।

उदाहरण 1:

• इनपुट: एन = 3
• आउटपुट: 3
• स्पष्टीकरण: प्रारंभ में, हमारे पास एक अक्षर 'ए' है।
  • चरण 1 में, हम कॉपी ऑल ऑपरेशन का उपयोग करते हैं।
  • चरण 2 में, हम 'एए' प्राप्त करने के लिए पेस्ट ऑपरेशन का उपयोग करते हैं।
  • चरण 3 में, हम 'एएए' प्राप्त करने के लिए पेस्ट ऑपरेशन का उपयोग करते हैं।

उदाहरण 2:

• इनपुट: एन = 1
• आउटपुट: 0

उदाहरण 3:

• इनपुट: एन = 10
• आउटपुट: 7

उदाहरण 2:

• इनपुट: एन = 24
• आउटपुट: 9

प्रतिबंध:

• 1

संकेत देना:

1. अंतिम चरण में क्लिपबोर्ड में कितने अक्षर हो सकते हैं यदि n = 3? एन = 7? एन = 10? एन = 24?

समाधान:

हमें स्क्रीन पर बिल्कुल n वर्ण 'ए' प्राप्त करने के लिए संचालन की न्यूनतम संख्या खोजने की आवश्यकता है। इसे प्राप्त करने के लिए हम एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे।

1. समस्या को समझना:

   • हम स्क्रीन पर एक 'ए' से शुरू करते हैं।
   • हम या तो "सभी कॉपी करें" (जो वर्तमान स्क्रीन सामग्री को कॉपी करता है) या "पेस्ट" (जो अंतिम कॉपी की गई सामग्री को पेस्ट करता है)।
   • हमें स्क्रीन पर बिल्कुल एन अक्षर 'ए' रखने के लिए आवश्यक न्यूनतम संचालन निर्धारित करने की आवश्यकता है।

2. गतिशील प्रोग्रामिंग दृष्टिकोण:

   • एक गतिशील प्रोग्रामिंग (डीपी) सरणी डीपी का उपयोग करें जहां डीपी[i] स्क्रीन पर बिल्कुल i अक्षर प्राप्त करने के लिए आवश्यक संचालन की न्यूनतम संख्या का प्रतिनिधित्व करता है।
   • डीपी[1] = 0 प्रारंभ करें क्योंकि स्क्रीन पर एक 'ए' रखने के लिए 0 ऑपरेशन लगते हैं।
   • 2 से n तक प्रत्येक वर्ण संख्या के लिए, i के प्रत्येक विभाजक की जाँच करके न्यूनतम संचालन की गणना करें। यदि i, d से विभाज्य है, तो:
     • i तक पहुंचने के लिए आवश्यक ऑपरेशंस की संख्या d तक पहुंचने के लिए ऑपरेशंस और i प्राप्त करने के लिए d को गुणा करने के लिए आवश्यक ऑपरेशंस का योग है।

3. समाधान के चरण:

   • dp[1] को छोड़कर सभी मानों के लिए INF (या एक बड़ी संख्या) के साथ एक DP सरणी प्रारंभ करें।
   • 2 से n तक प्रत्येक i के लिए, i के संभावित विभाजकों के माध्यम से पुनरावृति करें और कॉपी और पेस्ट करके i तक पहुंचने के लिए आवश्यक संचालन के आधार पर dp[i] को अपडेट करें।

आइए इस समाधान को PHP में लागू करें: 650। 2 कुंजी कीबोर्ड

स्पष्टीकरण:

• प्रारंभिकरण: प्रारंभ में पहुंच योग्य स्थिति का प्रतिनिधित्व करने के लिए डीपी को एक बड़ी संख्या (PHP_INT_MAX) के साथ प्रारंभ किया गया है।
• विभाजक जांच: प्रत्येक संख्या के लिए, सभी विभाजक की जांच करें। d तक पहुंचने के लिए आवश्यक संचालन पर विचार करके और फिर i प्राप्त करने के लिए गुणा करके dp[i] को अपडेट करें।
• आउटपुट: परिणाम dp[n] का मान है, जो स्क्रीन पर बिल्कुल n अक्षर प्राप्त करने के लिए आवश्यक न्यूनतम संचालन देता है।

यह दृष्टिकोण सुनिश्चित करता है कि हम दी गई बाधाओं के लिए न्यूनतम संचालन की कुशलतापूर्वक गणना करते हैं।

संपर्क लिंक

यदि आपको यह श्रृंखला उपयोगी लगी, तो कृपया रिपॉजिटरी को GitHub पर एक स्टार देने या पोस्ट को अपने पसंदीदा सोशल नेटवर्क पर साझा करने पर विचार करें। आपका समर्थन मेरे लिए बहुत मायने रखेगा!

यदि आप इस तरह की और अधिक उपयोगी सामग्री चाहते हैं, तो बेझिझक मुझे फ़ॉलो करें:

• लिंक्डइन
• गिटहब