[Solved] The Conversion To One Contest Problem

The Conversion To One: You are given a number N. You need to convert it to 1 in minimum number of operations.

The operations allowed are as follows:

• If N is even then divide the number by 2.
• If N is odd then you can either add 1 to it or subtract 1 from it.

Using the above operations, find the minimum number of operations require to convert N to 1.

The Conversion To One Contest

Input:
The first line of input contains T denoting the number of testcases. T testcases follow. Each testcase contains 1 line of input containing N.

Output:
For each testcase, in a new line, print the minimum number of steps required.

Constraints:
1 <= T <= 100
1 <= N <= 10⁷

Examples:
Input:
4
1
2
3
4
Output:
0
1
2
2

Explanation:
Testcase1: 1 can be converted into 1 in 0 steps.
Testcase2: 2 can be converted into 1 in 1 step: 2-1

Solution:

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {

    static int CountWays(int N) {

        if (N == 1) {
            return 0;
        }

        else if (N % 2 == 0) {
            return 1 + CountWays(N / 2);
        } else {
            return 1 + Math.min(CountWays(N - 1), CountWays(N + 1));
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-->0) {
            int n = sc.nextInt();
            System.out.println(CountWays(n));
        }

    }
}

#include <bits/stdc++. h>
using namespace std;

int CountWays(int N){
	
	if(N == 1){
		return 0;
	}
	
	else if(N%2 == 0){
		return 1 + CountWays(N/2);
	}else{
		return 1 + min(CountWays(N-1),CountWays(N+1));
	}
	
	
}

int main(){
	
	int T;
	cin>>T;
	
	while(T--){
		int N;
		cin>>N;
		cout<<CountWays(N)<<endl;
	}
}

#include <bits/stdc++.h>
using namespace std;


long long minOperations(long long n)
{
    if(n==1) 
    return 0; //since 1 is already 1
    if(n==2)
    return 1; //convert 2 to 1. 1 step
    if(n==3)
    return 2; //convert 3 to 2. Then 2 to 1. 2 steps
    long long total=0; //save total steps
    if(n%2!=0) //if odd
    {
          total=1+min(minOperations(n-1),minOperations(n+1)); 
          //convert n to n-1 or n+1 then minimum of those conversions
    }
    else
    total=1+minOperations(n/2); //convert n to n/2 then count operations required for n/2 to 1
    
    return total; //returning total at the end
}

int main() {
    int testcases;
    cin>>testcases;
    while(testcases--)
    {
        long long n;
        cin>>n;
        cout<<minOperations(n)<<endl;
        
        
    }
	return 0;
}

import java.io.*;
import java.util.*;

class GFG {
	public static void main (String[] args) {
	    
		Scanner sc=new Scanner(System.in);
		int testcases=sc.nextInt();
		
		while(testcases-->0)
		{
		    long n=sc.nextLong();
		    System.out.println(Geeks.minOperations(n));
		   
		}
	}
}

class Geeks
{
    public static long minOperations(long n)
    {
        if(n==1) 
        return 0; //since 1 is already 1
        if(n==2)
        return 1; //convert 2 to 1. 1 step
        if(n==3)
        return 2; //convert 3 to 2. Then 2 to 1. 2 steps
        long total=0; //save total steps
        if(n%2!=0) //if odd
        {
              total=1+Math.min(minOperations(n-1),minOperations(n+1)); 
              //convert n to n-1 or n+1 then minimum of those conversions
        }
        else
        total=1+minOperations(n/2); //convert n to n/2 then count operations required for n/2 to 1
        
        return total; //returning total at the end
    }
}

def minOperations(n):
    if n<=3:
        return n-1
    elif(n%2!=0):
        return (1+min(minOperations(n-1), minOperations(n+1)))
    else:
        return (1+minOperations(n//2))


if __name__=="__main__":
    t = int(input())
    while(t>0):
        n = int(input())
        print(minOperations(n))
        t=t-1

Happy Learning – If you require any further information, feel free to contact me.