hi, this problem makes you learn about space limits. if you make an integer array of say input 10^9, you are consuming approx 4GB memory, which might not be permissible. so you need to make a balance between time and space complexity.
the same problem can be accessed in https://www.hackerearth.com/practice/algorithms/dynamic-programming/state-space-reduction/practice-problems/algorithm/bytelandian-gold-coins/description/
here is the solution(wrt hackerearth problem):
/* IMPORTANT: Multiple classes and nested static classes are supported */
// * uncomment this if you want to read input.
//imports for BufferedReader
import java.io.BufferedReader;
import java.io.InputStreamReader;
//import for Scanner and other utility classes
import java.util.*;
// Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
class TestClass {
public static void main(String args[] ) throws Exception {
// Sample code to perform I/O:
//Use either of these methods for input
//BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String name;
try{
while((name = br.readLine())!=null){
//Scanner obj = new Scanner(System.in);
int a = Integer.parseInt(name);
long arr[] = new long[10000000];
for(int i=0;i<10000000;i++){
arr[i] = -1;
}
System.out.println(coins(arr,a));
}
}catch(Exception ex){} }
}
public static long coins(long[]arr, int n){
if( n<10000000 && arr[n]!=-1)
return arr[n];
if(n<12){
arr[n]=n;
return arr[n];}
long find = Math.max(n,coins(arr,n/4)+coins(arr,n/3)+coins(arr,n/2));
if(n<10000000) arr[n]=find;
return find;
}
}
have a look and try to understand the space limits.
thanks
