C++ प्रोग्राम संख्या n से 1 करने के लिए आवश्यक न्यूनतम संख्या में संचालन की गणना करने के लिए

मान लीजिए कि हमारे पास एक संख्या n है। हम इनमें से किसी एक ऑपरेशन को कई बार मनमाने ढंग से करते हैं -

n को n/2 से बदलें जब n 2 से विभाज्य हो
n को 2n/3 से बदलें जब n 3 से विभाज्य हो
n को 4n/5 से बदलें जब n 5 से विभाज्य हो

हमें नंबर 1 बनाने के लिए आवश्यक न्यूनतम चालों की संख्या गिननी होगी। यदि संभव नहीं है, तो -1 लौटें।

इसलिए, यदि इनपुट n =10 की तरह है, तो आउटपुट 4 होगा, क्योंकि 5 प्राप्त करने के लिए n/2 का उपयोग करें, फिर 4 प्राप्त करने के लिए 4n/5, फिर 2 प्राप्त करने के लिए n/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;
}