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

Last update on December 20 2024 12:24:11 (UTC/GMT +8 hours)

Write a C++ program to replace a given number until it becomes 1. If the given number(n) is even replace n with n/2 and if the 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;

// Function to determine the minimum number of replacements to reach 1 following the rules
long long num_replace(long long n) {
    // If the number is already 1, no replacements needed
    if (n == 1) return 0;

    // If the number is even, divide it by 2 and increment the replacement count by 1
    if (n % 2 == 0)
        return num_replace(n / 2) + 1;
    // If the number is odd, choose between (n+1) or (n-1) whichever requires fewer replacements, and increment the count by 1
    else
        return min(num_replace(n + 1), num_replace(n - 1)) + 1;
}

int main() {
    long n = 8; // Example: 8 -> 4 -> 2 -> 1
    // Calculate the number of replacements needed for 'n' to reach 1 following the rules
    cout << "\nOriginal number: " << n << "  Number of replacements: " <<  num_replace(n) << endl;      

    n = 10; // Example: 10 -> 5 -> 4 -> 2 -> 1
    // Calculate the number of replacements needed for 'n' to reach 1 following the rules
    cout << "\nOriginal number: " << n << "  Number of replacements: " <<  num_replace(n) << endl;  

    n = 12; // Example: 12 -> 6 -> 3 -> 2 -> 1
    // Calculate the number of replacements needed for 'n' to reach 1 following the rules
    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:

Click to Open Editor

Contribute your code and comments through Disqus.

Previous: Check whether a given positive integer is a perfect square or not.