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
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.