# Minimum Steps – Hacker Earth Problem Solution

There are three integers k,m,n. You have to convert the number k to m by performing the given operations:

• Multiply k by n
•  Decrease k by 2.
•  Decrease k by 1.
You have to perform the above operations to convert the integer from k to m and find the minimum steps.
Note: You can perform the operations in any order.
Input : –

First-line contains the number of test cases T.
The next T line contains three space-separated integers k, m, and n.
Output : –
Print minimum no. of steps as output in a new line for each test case.

In C –

#include<stdio.h>
int r(a,b,c)
{
if(a>=b)
{
return ((a-b)/2+(a-b)%2);
}
else if(b%c==0)
{
return (1+r(a,b/c,c));
}
else
{
int x=(b/c+1)*c;
return ((x-b)/2+(x-b)%2+r(a,x,c));
}
}
int main()
{
int t;
scanf(“%d”,&t);
for(int i=0;i<t;i++)
{
int k,m,n;
scanf(“%d %d %d”,&k,&m,&n);
printf(“%dn”,r(k,m,n));
}
return 0;
}

In C++ –

int step(int k,int m,int n)
{ int x;
if(k>=m)
return (k-m)/2+(k-m)%2;
if(m%n==0)
return (1+step(k,m/n,n));
else
{
x=(m/n+1)*n;
return ((x-m)/2+(x-m)%2+step(k,x,n));
}
}
#include<iostream>
using namespace std;
int main()
{
int t;
cin>>t;
for(int i=0;i<t;i++)
{ int k,m,n;
cin>>k>>m>>n;
cout<<step(k,m,n)<<endl;
}
return 0;
}

In Java –

import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;
class test
{
public static void main(String[] args) {
public void run() {
solve();
}
}, “1”, 1 << 26).start();
}
static void solve () {
int t =fr.nextInt() ; long k ,m ,n ,dm ,i ,j ,l ,mn ;
while (t–>0) {
k =fr.nextLong() ; m =fr.nextLong() ; n =fr.nextLong() ;
if (n>1) {
i =0 ; mn =Integer.MAX_VALUE ;
if (k<m) {
while (k<m) { ++i ; k*=n ; }
}
else {
dm =k-m ; mn =dm%2l + dm/2l ;
k *= n ; ++i ;
}
dm =k-m ; l =i ;
while (dm>0 && l>0) {
j =dm%n ; dm /= n ;
j =j%2l + j/2l ; i += j ;
–l ;
}
if (dm>0) i += (dm%2l + dm/2l) ;
op.println(Math.min(i,mn)) ;
}
else {
k -= m ; op.println((k%2l + k/2l)) ;
}
}
op.flush(); op.close();
}
StringTokenizer st;
}
String next() {
while (st==null || (!st.hasMoreElements()))
{
try
{
}
catch(IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
String nextLine() {
String str =””;
try
{
}
catch(IOException e)
{
e.printStackTrace();
}
return str;
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next()) ;
}
}
}

In Python –

def rec(a, b, c):
if a >= b:
return ((a-b)//2+(a-b)%2)
if b%c==0:
return (1 + rec(a,b//c,c))
else:
x=(b//c+1)*c;
return ((x-b)//2 + (x-b)%2 + rec(a,x,c))
t = int(input())
while t > 0:
a, b, c = map(int, input().split())
print(rec(a, b, c))
t -= 1
Sharing Is Caring