मान लीजिए हमारे पास एक संख्या n है। हम इनमें से कोई एक संक्रिया मनमाने ढंग से कई बार करते हैं:
n को n/2 से बदलें जब n 2 से विभाज्य हो
n को 2n/3 से बदलें जब n 3 से विभाज्य हो
n को 4n/5 से बदलें जब n 5 से विभाज्य हो
हमें संख्या 1 बनाने के लिए आवश्यक न्यूनतम चालों की संख्या गिननी है। यदि संभव नहीं है, तो -1 वापस करें।
उदाहरण के लिए, यदि इनपुट n = 10 है, तो आउटपुट 4 होगा, क्योंकि n/2 का उपयोग करके 5 प्राप्त करें, फिर 4n/5 से 4 प्राप्त करें, फिर n/2 फिर से 2 प्राप्त करने के लिए और n/2 फिर से 1 प्राप्त करने के लिए।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
m := 0 while n is not equal to 1, do: if n mod 2 is same as 0, then: n := n / 2 (increase m by 1) otherwise when n mod 3 is same as 0, then: n := n / 3 m := m + 2 otherwise when n mod 5 is same as 0, then: n := n / 5 m := m + 3 Otherwise m := -1 Come out from the loop return m
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int solve(int n) { int m = 0; while (n != 1) { if (n % 2 == 0) { n = n / 2; m++; } else if (n % 3 == 0) { n = n / 3; m += 2; } else if (n % 5 == 0) { n = n / 5; m += 3; } else { m = -1; break; } } return m; } int main() { int n = 10; cout << solve(n) << endl; }
इनपुट
10
आउटपुट
4
