मान लीजिए हमारे पास दो पूर्णांक N और M हैं। हमें N से M तक पहुंचने के लिए न्यूनतम चरणों की संख्या खोजनी है, दिए गए ऑपरेशन करके -
- संख्या x को 2 से गुणा करें, तो x 2*x हो जाएगा
- संख्या x से एक घटाएं, तो संख्या x - 1 हो जाएगी
यदि N = 4 और M = 6, तो आउटपुट 2 होगा। तो यदि हम ऑपरेशन नंबर 2 को N पर करते हैं, तो N 3 बन जाता है, फिर ऑपरेशन नंबर 1 को N के अपडेटेड मान पर करते हैं, तो यह 2 * 3 = 6 हो जाता है। तो न्यूनतम चरणों की संख्या 2 होगी।
इस समस्या को हल करने के लिए, हम इन नियमों का पालन करेंगे -
- हम समस्या को उल्टा कर सकते हैं, जैसे हम N से शुरू करने के बजाय M से शुरू करते हैं, तो दो नए ऑपरेशन होंगे
- संख्या को 2 से विभाजित करें, जब यह सम हो,
- संख्या में 1 जोड़ें
- अब न्यूनतम ऑपरेशनों की संख्या होगी
- यदि N > M, तो उनके बीच का अंतर वापस करें, तो चरणों की संख्या M में 1 जोड़ना होगा, जब तक यह N के बराबर न हो जाए
- अन्यथा जब N < M, M को 2 से विभाजित करते रहें, जब तक यह N से कम न हो जाए। यदि M विषम है, तो पहले इसमें 1 जोड़ें, फिर 2 से विभाजित करें, एक बार M, 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
