SKhurana - 3 months ago 11x
Java Question

# How to chain elements in array in dynamic programming (java)

I have a dynamic algorithm problem and I have almost solved it. The problem is I have a primitive calculator which can only do operations of adding 1, multiplying by 2 and multiplying by 3. I have to find the minimum number of steps required to get to any number. I have implemented the problem correctly but I also have to output the array of numbers which lead to n. That means, for example, for n=5, the steps are 1, 2, 4, 5 and I have to output 3 since it took 3 steps. My algorithm works in finding the minimum amount of steps but I can't find the array. I am thinking that a divide and conquer algorithm which starts from the end might work but I am not good in divide and conquer. Here is my code. It outputs the entire array(all the elements, not the elements just leading to n).

``````public static int min(int a, int b){if(a>b){return b;}else{return a;}}
public static int min(int a, int b, int c){return min(min(a, b), c);}
public static int[] primitiveCalc(int n){
int[] solution=new int[n];
solution[0]=0;
solution[1]=0;
for(int i=2;i<n;i++){
if(i%3==0){
if(i%2==0){solution[i]=min(solution[i-1]+1, solution[i/3]+1, solution[i/2]+1);}
else{solution[i]=min(solution[i-1]+1, solution[i/3]+1);}
}else if(i%2==0){solution[i]=min(solution[i-1]+1, solution[i/2]+1);}
else{solution[i]=solution[i-1]+1;}
}
System.out.println(solution[n-1]);
return solution;
}
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[] solution=primitiveCalc(n+1);
for(int i=1;i<solution.length;i++){
System.out.print(solution[i]+" ");
}
}
``````

any help is appreciated.

I got the solution, here is the implementation if anyone is interested :

``````public static int[] findChainArray(int[] array, int n){
int[] chainedArr=new int[array.length];
for(int i=array.length-1, j=0;i>0;j++){
if(i%3==0) {
if (i % 2 == 0) {
if (min(array[i - 1], array[i / 2], array[i / 3]) == array[i - 1]) {
i = i - 1;
} else if (min(array[i - 1], array[i / 2], array[i / 3]) == array[i / 2]) {
i = i / 2;
} else {
i = i / 3;
}
}else{
if (min(array[i - 1], array[i / 3]) == array[i - 1]) {
i = i - 1;
} else {
i = i / 3;
}
}
}else if(i%2==0){
if (min(array[i - 1], array[i / 2]) == array[i - 1]) {
i = i - 1;
} else if (min(array[i - 1], array[i / 2]) == array[i / 2]) {
i = i / 2;
}
}else{
i=i-1;
}
chainedArr[j]=i;
}
return chainedArr;
}
``````

i know there are way too many if else and il try to reduce that

You can work recursively from `answer = solution[n]` and check to see if `solution[n-1] = answer-1`, `solution[n/2] = answer-1`, or `solution[n/3] = answer-1`. Of course you'd need to do the proper checks to see if `n` is divisible by `2` or `3` first, as you have been doing already.
Alternatively, you can create an array called `last` and instead of only saving the minimum value for each `i` in `solution`, you could also save the last element in the path in `last`.