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

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

• Shouldn't steps be initialized to 1 ? – KaushikTD Dec 2 '20 at 19:42

## 1 Answer

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