In C++, reduce a number to 1 by performing the given operation

Given an integer as input. The goal is to find the minimum number of steps or operations required to reduce the input Number to 1. The operations that can be performed would be -:

• If Number is even, then divide it by 2.

• If Number is odd, increment or decrement it by 1.

Example

Input− Number=28

Output− Reduce 28 to 1: Minimum steps of 6

Explanation−

28 is an even number - divide by 2 = 14

14 is an even number - divide by 2 = 7

7 is an odd number - divide by 1 = 8

8 is an even number - divide by 2 = 4

4 is an even number - divide by 2 = 2

2 is an even number - divide by 2 = 1

Input − Number=9

Output − Minimum steps to reduce 9 to 1: 4

Explanation -

9 is an odd number - subtract 1 = 8

8 is an even number - divide by 2 = 4

4 is Even number - divide by 2 = 2

2 is an even number - divide by 2 = 1

The method used in the following program is as follows

2 is an even number - divide by 2 = 1 h2>

In this method, use a recursive method to check the minimum operations required to reduce Number to 1. Minimal way to recursively check for Number 1 or Number-1 (whichever is smaller) if it's even a simple division by 2.

• Treats the input Number as an integer.

• The function minWays(int num) takes num as input and returns the minimum number of operations required to reduce num to 1.

• Take the variables tmp1, tmp2 and min as integers.

• If num is 0, return 1.

• If num%2==0 is an even number, set num=num/2

• If num is an odd number, set tmp1= minWays(num-1) and tmp2=minWays(num 1).

• Set min to be the minimum value of tmp1 and tmp2.

• Return 1 min.

• In the end we will get the desired result.

• Print the results in main.

Example

#include <iostream>
using namespace std;
int minWays(int num){
   int tmp1,tmp2,min;
   if (num == 1){
      return 0;
   }
   else if (num % 2 == 0){
      tmp1=minWays(num/2);
      return (1 + tmp1);
   }
   else{
      int tmp1=minWays(num - 1);
      int tmp2=minWays(num + 1);
      int min=tmp1<tmp2?tmp1:tmp2;
      return (1 + min);
   }
}
int main(){
   int Number = 21;
   cout <<"Minimum steps to reduce "<<Number<<" to 1: "<<minWays(Number);
   return 0;
}

Output

If we run the above code it will generate the following output

Minimum steps to reduce 21 to 1: 6

The above is the detailed content of In C++, reduce a number to 1 by performing the given operation. For more information, please follow other related articles on the PHP Chinese website!