Minimum Steps - HackerEarth 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("%d\n",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.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.PrintWriter;

import java.util.StringTokenizer;

class test

{

public static void main(String[] args) {

new Thread(null, new Runnable() {

public void run() {

                solve();

            }

        }, "1", 1 << 26).start();

}

static void solve () {

   FastReader fr =new FastReader(); PrintWriter op =new PrintWriter(System.out);

  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();

}

static class FastReader {

BufferedReader br;

StringTokenizer st;

public FastReader() {

br =new BufferedReader(new InputStreamReader(System.in));

}

String next() {

while (st==null || (!st.hasMoreElements())) 

{

try

{

st =new StringTokenizer(br.readLine());

}

catch(IOException e)

{

e.printStackTrace();

}

}

return st.nextToken();

}

String nextLine() {

String str ="";

try

{

str =br.readLine();

}

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