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

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]; 
}