# Leetcode: Integer Replacement

Integer Replacement

Similar Problems:

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
```

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution: Recursive + pruning
```// Blog link: https://code.dennyzhang.com/integer-replacement
// Basic Ideas: recursive + pruning
// Complexity: Time O(n), Space O(n)
var m map[int]int
func integerReplacement(n int) int {
m = map[int]int{}
d := 0
for i:=1; i<=n*2; i=i*2 {
m[i] = d
d++
}
return getDistance(n)
}

func getDistance(n int) int {
v, ok := m[n]
res := -1
if ok { return v }
if n%2 == 0 {
res = 1+getDistance(n/2)
} else {
v1, v2 := getDistance(n-1)+1, getDistance((n+1)/2)+2
res = v1
if v1>v2 { res = v2 }
}
m[n] = res
return res
}
```

• Solution: BFS + pruning
```// Blog link: https://code.dennyzhang.com/integer-replacement
// Basic Ideas: BFS + pruning
// Complexity: Time O(n), Space O(n)
func integerReplacement(n int) int {
m := map[int]int{}
d := 0
for i:=1; i<=n*2; i=i*2 {
m[i] = d
d++
}
v, ok := m[n]
if ok { return v }

queue := []int{n}
res := 1<<31 - 1
d = 0
for len(queue) != 0 {
l := []int{}
for _, v := range queue {
l2 := []int{}
if v % 2 == 0 {
l2 = append(l2, v/2)
} else {
l2 = append(l2, v+1)
l2 = append(l2, v-1)
}
for _, num := range l2 {
_, ok := m[num]
if ok {
m[v] = m[num] + 1
if res > m[v] + d {
res = m[v] + d
}
} else {
l = append(l, num)
}
}
}
queue = l
d++
}
return res
}
```

Share It, If You Like It.