SKhurana SKhurana - 4 months ago 26
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

Answer

Now that you have a valid path, you could try working backwards.

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.

Since this seems like either a homework problem or a question that you're trying to work through on your own, I'll leave the implementation details up to you :)