Minimum Steps – Hacker Earth Problem Solution

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.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

Leave a Comment