Minimum steps to 1 to find minimum operations to transform n to 1

Question

I was doing this JavaScript problem called "Minimum steps to 1." You can find the problem here.

Given a positive integer - num, Following is a list of possible operations which can be performed on it:

1. num / 2, If number is divisible by 2
2. num / 3, If number is divisible by 3
3. num - 1

With these 3 available operations, find out the minimum number of steps required to reduce the number to 1.

For example:

1. For num = 1, no. of steps needed - 0
2. For num = 2, no. of steps needed - 1 (num/2)
3. For num = 6, no. of steps needed - 2 (num/3 followed by num/2)
4. For num = 9, no. of steps needed - 2 (num/3 followed by num/3)

function minStepstoOne(n) {
 let steps = [];
 steps[0] = 0; 
 steps[1] = 0; 
 for(let i = 2; i <= n; i ++) {
 let minChoice = steps[i - 1]; 
 if(i % 2 == 0) {
 let divideByTwo = steps[i/2]
 minChoice = Math.min(divideByTwo, minChoice); 
 }
 if(i % 3 == 0) {
 let divideByThree = steps[i/3]
 minChoice = Math.min(divideByThree, minChoice); 
 }
 steps[i] = minChoice + 1;
 }
 return steps[n]; 
}
//console.log(minStepstoOne(9)); 

• KaushikTD: Shouldn't steps[1] be initialized to 1 ?

Answer 1

Your function is right.

However, for dynamic programming I always propagate state n to all states n+1 (Forward). Your code calculates state n+1 from state n (Backward). In this case both methods are okay and it is mostly a personal preference. But in other cases the backward method may run into problems that state n is not yet calculated.

function minStepstoOne2(n) {
 var steps = Array(n+1).fill(n);
 steps[1] = 0; 
 for(let i = 1; i < n; i ++) {
 steps[i + 1] = Math.min(steps[i + 1], steps[i] + 1); 
 if (i * 2 <= n)
 steps[i * 2] = Math.min(steps[i * 2], steps[i] + 1); 
 if (i * 3 <= n)
 steps[i * 3] = Math.min(steps[i * 3], steps[i] + 1); 
 }
 return steps[n]; 
}