C++ program to calculate the minimum number of operations required to change a number n to 1

Suppose we have a number n. We arbitrarily perform one of these operations -

• When n is divisible by 2, replace n with n/2

• When n is divisible by 2 When n is divisible by 3, replace n with 2n/3

• When n is divisible by 5, replace n with 4n/5

  li>

We must calculate the minimum number of moves required for the number 1. If not possible, -1 is returned.

So if the input is something like n = 10, the output will be 4 because using n/2 we get 5, then we use 4n/5 to get 4, then n/2 again we get 2, and again n/2 Got 1.

Steps

Steps h2>

To solve this problem we will follow the following steps-

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

Example

Let’s see Following implementation for better understanding -

#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;
}

input

10

output

4

The above is the detailed content of C++ program to calculate the minimum number of operations required to change a number n to 1. For more information, please follow other related articles on the PHP Chinese website!