C++ Exercises: Replace a given number until it become 1

C++ Math: Exercise-31 with Solution

Write a C++ program to replace a given number until it become 1. If the given number(n) is even replace n with n/2 and if the given number(n) is odd replace n with either n+1 or n-1. Find the minimum number of replacements.

Sample Input: n = 8
Number of replacements: 3
Sample Input: n = 10
Number of replacements: 4

Sample Solution:

C++ Code :

#include <iostream>
#include <cmath>

using namespace std;
  
    long long num_replace(long long n) 
    {
        if (n==1) return 0;
        
        if (n%2==0)
            return num_replace(n/2)+1;
        else
            return min(num_replace(n+1), num_replace(n-1))+1;
    }    
int main() 
{
    long n = 8; // 8 -> 4 -> 2 -> 1
    cout << "\nOriginal number: "<< n << "  Number of replacements: " <<  num_replace(n) << endl;      
    n = 10; // 10 -> 5 -> 4 -> 2 -> 1
    cout << "\nOriginal number: "<< n << "  Number of replacements: " <<  num_replace(n) << endl;      
    n = 12; // 12 -> 6 -> 3 -> 2 -> 1
    cout << "\nOriginal number: "<< n << "  Number of replacements: " <<  num_replace(n) << endl;      
    
	return 0;    
}

Sample Output:

Original number: 8  Number of replacements: 3

Original number: 10  Number of replacements: 4

Original number: 12  Number of replacements: 4

Flowchart:

C++ Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a C++ program to check whether a given positive integer is a perfect square or not.