SKhurana - 6 months ago 38

Java Question

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 :)