COAD03 - Editorial

general
, ,
1

Problem Code: COAD03

Problem Link is here

Problem Name: Mr Thakkar want to go dream land

Contest Name: CodeAdda Practice Contest – 2 (CPC2016)

Author : Yatharth Oza (Username: yatharth100)

Difficulty: Easy

PREREQUISITES: DP

Problem:

In input a number ‘n’ is given in each test case. Mr. Thakkar wants to go to that numbered island by using 2 operations

  1. X+1 by 1 pound

  2. X*2 by 2 pounds

Where X is Mr. Thakkar current island. You need to find minimum number of cost to reach island number ‘n’.

Quick Explanation:

You need to use dynamic programming bottom up approach here. Find from 0 to 1 to 2 to 3……to n. So, maintain all record in an array and extract it when needed.

Explenation:

For this Problem we can apply bottom up approach of dynamic programming. For any input we will consider results of base case like for 0 output will be 0,
Now for 1 : hence it is not divisible by 2, so x+1 operation can be performed so 1 pound will be answer.
And so on……

You can also do this by dynamic programming tabulation method as shown below for n=11,(initially x=0)

X-value    Answer for all values**
X=0	        0
X=1	       (ans for 0)+1=1
X=2	       Min( (ans for 1)+1 , (ans for 0)+2 ) = 2
X=3	       (ans for 2)+1=3
X=4	       Min( (ans for 3)+1 , (ans for 2)+2 ) = 4
X=5	       (ans for 4)+1=5
X=6	       Min( (ans for 5)+1 , (ans for 3)+2 ) = 5
X=7	       (ans for 6)+1=6
X=8	       Min( (ans for 7)+1 , (ans for 4)+2 ) = 6
X=9	       (ans for 8)+1=7
X=10       Min( (ans for 9)+1 , (ans for 0)+2 ) = 7
X=11       (ans for 10)+1=8

Thus, the ans for n=11 is 8 which is minimum cost to reach the island.

Solution:

/*This solution is in JAVA and file name is fibonacci_analysis.java */
import java.util.*;
import java.lang.*;
import java.io.*;
class fibonacci_analysis {
    public static void main(String args[]) throws IOException{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 
int arr[]=new int[1001];
for(int i=1;i<1001;i++){
    arr[i]=arr[i-1]+1;
     if(i%2==0){
        arr[i]=Math.min(arr[i],arr[i/2]+2);
    }
}
 int aa=Integer.parseInt(br.readLine());
    for(int i=0;i<aa;i++){
        int n=Integer.parseInt(br.readLine());
      System.out.println(arr[n]);
      
    }
    }
}
2

import java.io.IOException;
import java.util.*;
public class firstdp {
public static void main(String[] args)throws IOException {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
int dp[]=new int[1001];
while(t>0)
{
int n=sc.nextInt();

       for(int i=1;i<=n;i++)
       {
           if(i%2==1)
               dp[i]=dp[i-1]+1;
           else dp[i]=Math.min(dp[i-1]+1,dp[i/2]+2);
       }
       System.out.println(dp[n]);
        t--;
    }

}