# Integer replacement algorithm

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

- If
*n*is even, replace*n*with*n*/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

Anonymous Answered question

Below is a simple self explanatory recursive algorithm using javascript

/** * @param {number} n * @return {number} */ var integerReplacement = function(n, count = 0) { if (n === 1) return count; if (n % 2 === 0) count = integerReplacement(Math.round(n/2), count+1); else count = Math.min(integerReplacement(n-1, count+1), integerReplacement(n+1, count+1)); return count; };

goli202084 Changed status to publish