COAD03 - Editorial

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



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.


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.


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

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

       for(int i=1;i<=n;i++)
           else dp[i]=Math.min(dp[i-1]+1,dp[i/2]+2);