You have a block of platinum that can be exchanged in your bank either for cash
or for smaller blocks of platinum. If you exchange a block of m grams, you get
three blocks of weight m/2, m/3 and m/4 grams each. You don’t get any fractional
part, as the division process rounds down the value. If you exchange the block of
platinum for cash, you get m units of currency. You can do any number of
exchanges for smaller blocks or currency.
Given the value of a block in grams as input, write a program that would print the
largest possible currency value that you can receive as the output. Assume that
the maximum value of a block that can be given as an input is 1,000,000,000
grams and the minimum value is 2 grams.
Sample input 1:
12
Sample output 1:
13
Explanation: You can change 12 into blocks of 12/2 = 6, 12/3 = 4 and 12/4 = 3,
and then exchange these for 6 + 4 + 3 = 13 units of currency
4
Sample input 2: 2
Sample output 2: 2
Explanation: If you exchange 2 grams into smaller blocks, it gives 2/2 = 1, 2/3 =
0, 2/4 = 0, only 1 unit. Instead, you can directly exchange the block for 2 units of
currency.
1 Like
here is the code which i tried in JAVA .how to make it more efficient ? in the below code i am only able to code it to exchange the blocks for cash & i am not getting how to exchange it for blocks of smaller platinums ?? plz help!!
import java.util.* ;
class Platinum
{
public static void main(String args[ ])
{
int m ; // m is no. of blocks of platinum
Scanner ob=new Scanner(System.in);
System.out.println("enter the no of blocks of platinum you want to
exchange between 2 and 1000,000,000 included:");
m=ob.nextInt();
if(m<2 || m>1000000000 )
{
System.out.println("You have entered a number out of the range
specified! \n");
System.out.println("Please Enter number between 1 and 1000000000
included: \n");
}
else if(m==2)
{ System.out.println("you can exchange "+m +" blocks of platinum for
"+ m +" units of currency");
System.exit(0);
}
else
{
System.out.println("no of blocks of platinum you want to
exchange:"+m);
}
int a=m/2;
int b=m/3;
int c=m/4;
int d=a+b+c;
System.out.println("you can exchange "+m +" blocks of platinum for "+ d
+" units of currency");
}
}
you can do it by recursion for example. let’s define a function f that tells how much money you can obtain from N amount of platinum. the problem is obviously to find the value of f(N). let’s have a look. you can either split your amount of platinum in 3 parts (N/2, N/3, N/4) thus getting f(N/2) + f(N/3) + f(N/4) units of currency, or exchanging all the amount, getting N units of currency. thus, it seems that f(N) = max( f(N/2) + f(N/3) + f(N/4), N ). am i right ? it should now be pretty easy to solve, as you just got a direct formula. if you read the comment i posted above, it should become really clear for you. good luck 
1 Like
@cyberax
hey can u check the code which i have already coded …posted above which is successfully compiling or checkout this link text
and let me know what can i do to improve it if u know java…
did you see my previous answer ? it seems you missed it : i don’t see any recursive/memoization/dp function in your code. moreover, all the debug strings you print on standard output are not mentionned in the problem statement, meaning you probably shouldn’t print them. please try to implement the f function, and after that new step, i’ll give you some other hints, and so on until your code works. good luck.
solved:
import java.util.* ;
class Factorial {
int fact(int m)
{
if(m<2) return 0;
int result= Math.max(fact(m/2)+fact(m/3)+fact(m/4),m);
System.out.println(result);
return result;
}
}
class Recursion {
public static void main (String args[]) {
Factorial f =new Factorial();
int m ; // m is no. of blocks of platinum
Scanner ob=new Scanner(System.in);
System.out.println("enter the no of blocks of platinum you want to exchange between 2 and 1000,000,000 included:");
m=ob.nextInt();
if(m<2 || m>1000000000 )
{
System.out.println("You have entered a number out of the range specified! \n");
System.out.println("Please Enter number between 2 and 1000000000 included: \n");
}
else if(m==2)
{
System.out.println("you can exchange "+m +" blocks of platinum for "+ m +" units of currency");
System.exit(0);
}
else
{
int result=f.fact(m);
System.out.println("you can exchange "+m +" blocks of platinum for "+ result +" units of currency");
}
}
}
You should have a look at this problem : COINS Problem - CodeChef . It is quite similar. Maybe comments and posted solutions will give you a hint. good luck.
save your java file as Recursion.java and paste the above code…it will work…