397.Integer Replacement

Tags: [recursion], [brute_force]

Link: https://leetcode.com/problems/integer-replacement/?tab=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 + 1or 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: brute_force, recursion

import sys

class Solution(object):
    def integerReplacement(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0:
            raise ValueError('the input is invalid')

        return self.integer_replacement_helper(n, 1, 0)

    def integer_replacement_helper(self, n, target, num_of_steps):
        # base case
        if n <= 0:
            return sys.maxint
        if n == target:
            return num_of_steps

        if n & 1 == 0:
            return self.integer_replacement_helper(n / 2, target, num_of_steps + 1)
        else:
            return min(self.integer_replacement_helper(n - 1, target, num_of_steps + 1),
                       self.integer_replacement_helper(n + 1, target, num_of_steps + 1))

Revelation:

• Brute force: try all possible ways to replace the integers.

Note:

• Time complexity = O(lgn + 2^lgn) = O(n), n is the user input. An = A1*q^(x - 1), A1 = n, An = 1, q = 1/2, so x = lgn. So if during the each step, we generate an even number, there should be lgn even numbers, but before or after getting the even number, we must get an odd number, so there are lgn odd numbers, and for even number there is only one way, for odd numbers there are two ways. So T = O(lgn + 2^lgn) = O(lgn + n) = O(n).