Moar dynamic programming

min-steps-to-one.js

// Given an integer n, find the minimum number of steps
// to reach integer 1.
// At each step, you can:
// * n - 1
// * n / 2, if it is divisble by 2
// * n / 3, if it is divisble by 3

// n = 0: 0 // base case 0.
// n = 1: 0 // base case 1.
// n = 2: 1 // base case 2.
// n = 3: 1 // base case 3.
// n = 4:
// * 4 ..-1..> 3 => 1 + x[3] = 1 + 1 = 2
// * 4 ../2..> 2 ==> 1 + x[2] = 1 + 1 = 2
// * 4 ../3..> Infinity
// ∆ min(2, 2) = 2;

// Time complexity: O(n) where n is the input value,
//                  e.g. 4. Then we need to find all combinations from 0 to n;
// Space complexity: O(n) where n is the number of combinations stored,
//                   e.g. input = 4. [4: Infinity] will be allocated to store the result.
function minStepsToOne(x) {
  if (x < 4) return x < 2 ? 0 : 1;

  const r = Array.from(Array(x + 1), (_, i) => {
    if (i < 2) return 0;
    if (i < 4) return 1;
    return Infinity;
  });

  for (let i = 4; i < x + 1; i += 1) {
      r[i] = Math.min(
        1 + r[i - 1],
        i % 2 === 0 ? 1 + r[i / 2] : Infinity,
        i % 3 === 0 ? 1 + r[i / 3] : Infinity
      );
  }

  return r[x];
}

function main() {
  const a = Array.from(Array(20), (_, i) => i);

  a.forEach((n) => {
    console.log(n, minStepsToOne(n));
  });
}

console.clear();
main();