C++ में N से M तक पहुँचने के लिए न्यूनतम चरणों की संख्या ज्ञात कीजिए

मान लीजिए कि हमारे पास दो पूर्णांक N और M हैं। हमें दिए गए संक्रियाओं को निष्पादित करके N से M तक पहुंचने के लिए न्यूनतम चरणों की संख्या ज्ञात करनी होगी -

• संख्या x को 2 से गुणा करें, तो x 2*x होगा
• संख्या x में से एक घटाएं, तो संख्या x - 1 होगी

यदि एन =4 और एम =6, तो आउटपुट 2 होगा। इसलिए यदि हम एन पर ऑपरेशन नंबर 2 करते हैं, तो एन 3 हो जाता है, फिर एन के अपडेटेड वैल्यू पर ऑपरेशन नंबर एक करें, तो यह 2 * 3 =6 हो जाता है। तो चरणों की न्यूनतम संख्या 2 होगी।

इस समस्या को हल करने के लिए, हम इन नियमों का पालन करेंगे -

• हम समस्या को उलट सकते हैं, जैसे हम M से शुरू होने वाली संख्या N लेते हैं, इसलिए नए दो ऑपरेशन होंगे
• 
  
  • संख्या को 2 से विभाजित करें, जब यह सम हो,
  • संख्या के साथ 1 जोड़ें
• अब संचालन की न्यूनतम संख्या होगी
  • यदि N> M, उनके बीच का अंतर लौटाएं, तो चरणों की संख्या M में 1 जोड़ देगी, जब तक कि वह N के बराबर न हो जाए
  • अन्यथा जब N

उदाहरण

#include<iostream>
using namespace std;
int countMinimumSteps(int n, int m) {
   int count = 0;
   while(m > n) {
      if(m % 2 == 1) {
         m++;
         count++;
      }
      m /= 2;
      count++;
   }
   return count + n - m;
}
int main() {
   int n = 4, m = 6;
   cout << "Minimum number of operations required: " << countMinimumSteps(n, m);
}

आउटपुट

Minimum number of operations required: 2