3
\$\begingroup\$

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)); 
\$\endgroup\$
1
\$\begingroup\$

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]; 
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.