Integer Replacement

Description

Given a positive integer n and you can do operations as follow:

1. If n is even, replace n with n/2.
2. If n is odd, you can replace n with either n + 1 or n - 1.

What is the minimum number of replacements needed for n to become 1?

Example 1:

Input:
8
Output:
3
Explanation:
8 -> 4 -> 2 -> 1

Example 2:

Input:
7
Output:
4
Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

Solution(javascript)

/*
 * @lc app=leetcode id=397 lang=javascript
 *
 * [397] Integer Replacement
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
const integerReplacement = function (n) {
  const memo = []
  const aux = (n) => {
    if (memo[n] !== undefined) {
      return memo[n]
    }
    if (n === 1) {
      return 0
    }
    if (n <= -2) {
      return Infinity
    }
    if (n % 2 === 0) {
      return 1 + aux(n / 2)
    }
    memo[n] = 1 + Math.min(
      aux(n - 1),
      aux(n + 1),
    )
    return memo[n]
  }
  return aux(n)
}
// @lc code=end