Convert Number n to 1 in Minimum Steps

Given a number n (n>=1 && n<=10¹⁸), your task is to convert it to 1 in minimum operation and constant space and time complexity. In one operation you can either –

Subtract 1 from n if n>1. (or)
Divide n by one of its proper divisor.

Examples:-

Input: n=2
Output: 1
2–>1.

first move:- subtract 1 from n , n=2-1=1.

Input: n=9
Output: 3
9–>8–>2–>1.

first move:- subtract 1 from n , n=9-1=8.
second move:- divide n by its one of proper divisor, n=8/4=2.
third move:- subtract 1 from n , n=2-1=1.

Naive Approach :-
We can use recursion to solve this problem .In each step we make 2 recursive call, one for subtracting 1 from n and second for dividing n by proper divisor. Base case will be when n=1.

Time complexity :- exponential.

Optimal Solution:-
This problem can be solved using greedy method and mathematics. There are 3 cases in this problem. let us discuss each of them.

Case 1:- when n<=3
for n<=3 the answer is clearly 0,1,2 for n=1,2,3.

Case 2:- when n>3 && n is odd
In such cases , the optimal solution can be obtained using following moves.
First move:- convert n to a even number by subtracting 1 from it ..it will cost 1 move.
Second move:- divide n by n/2. since n is even , So n/2 will definitely be a proper divisor of n.
Third move:- subtract 1 from n and it will become 1. Hence required number of moves are 3 for a odd number .

Case 3:- when n>3 && n is even
In such cases , the optimal solution can be obtained using following moves.

First move:- divide n by n/2. since n is even , So n/2 will definitely be a proper divisor of n.
Second move:- subtract 1 from n and it will become 1. Hence required number of moves are 2 for a even number .

Below is the implementation of the above approach:

#include <iostream>
using namespace std;

void minMoves(long long int n) {
    cout << n << " --> ";
    if (n % 2 == 1) {
        n--;
        cout << n << " --> ";
        n /= 2;  // Fixed the incorrect operation
        cout << n << " --> ";
        n--;
        cout << n << endl;
    } else {
        n /= 2;  // Fixed the incorrect operation
        cout << n << " --> ";
        n--;
        cout << n << endl;
    }
}

int main() {
    minMoves(242);
    minMoves(163);
    minMoves(102939243);
    minMoves(7);
    return 0;
}

Output:

242-->2-->1
163-->162-->2-->1
102939243-->102939242-->2-->1
7-->6-->2-->1

Time Complexity:- O(1)
Space Complexity:- O(1)