Leetcode 397 - Integer repalcement

Note:

  • A really typical DFS + Memo problem.

Question:

Given a positive integer n, you can apply one of the following operations:

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

Return the minimum number of operations needed for n to become 1.

Example:

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

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @param {number} n
* @return {number}
*/
var integerReplacement = function(n) {
let memo = {};
return dfs(n);

function dfs(num) {
if (memo[num]) return memo[num];
if (num === 1) return 0;
if (num % 2 === 1) {
const add1 = 1 + dfs(num + 1);
const minus1 = 1 + dfs(num - 1);
memo[num] = Math.min(add1, minus1);
} else {
const divide = 1 + dfs(num / 2);
memo[num] = divide;
}
return memo[num];
}
};