Python O(log n) time, O(1) space with explanation and proof


  • 15
    B

    Denote f(n) the minimum number of jumps from n to 1.
    By definition, we have the recurrence
    f(1) = 0, f(2n) = 1 + f(n), f(2n + 1) = min(f(2n) + 1, f(2n + 2) + 1).
    First notice that this sequence is well defined because f(2n + 2) = f(n + 1) + 1, so f(2n + 1) = min(f(2n) + 1, f(n + 1) + 2). Every element is defined by some element before it.
    We want to show (*):
    If n % 4 = 3 and n != 3, then f(n) = f(n + 1) + 1.
    If n % 4 = 1 or n = 3, then f(n) = f(n - 1) + 1.
    This gives us an O(log n) time, O(1) space solution.

    class Solution(object):
        def integerReplacement(self, n):
            rtn = 0
            while n > 1:
                rtn += 1
                if n % 2 == 0:
                    n //= 2
                elif n % 4 == 1 or n == 3:
                    n -= 1
                else:
                    n += 1
            return rtn
    

    In this code, n will drop to at most n / 2 in at most 2 iterations, so the number of iterations is at most 2 * log(n). In each iteration, the time complexity is constant. So the overall time complexity is O(log n). The space complexity is obviously 1. Correctness is guaranteed by (*).

    Lemma 1. f(k+1) <= f(k) + 1
    Prove by induction:
    f(2) = 1 <= 0 + 1 = f(1) + 1
    Assume this hold for any 1 <= k' < k,
    If k is even, f(k + 1) = min(f(k) + 1, f(k + 2) + 1) <= f(k) + 1;
    If k is odd, denote k = 2l + 1 (l >= 1), then f(k + 1) = f(2l + 2) = 1 + f(l + 1) <= 1 + 1 + f(l) = 1 + f(2l) = 1 + f(k - 1). Also, f(k + 1) = 1 + f(l + 1) = f(2l + 2) = f(k + 1) <= f(k + 1) + 1. Hence, f(k + 1) <= min(f(k - 1) + 1, f(k + 1) + 1) = f(k) <= f(k) + 1.

    Lemma 2. f(k) <= 1 + f(k + 1), k >= 1
    Prove by induction:
    f(1) = 0 <= 1 + f(2)
    Assume this hold for any 1 <= k' < k,
    If k is odd, f(k) = min(1 + f(k - 1), 1 + f(k + 1)) <= 1 + f(k + 1)
    If k is even, denote k = 2l (l >= 1), then f(k) = f(2l) = 1 + f(l)
    1 + f(l) <= 3 + f(l) = 2 + f(2l) = 1 + (1 + f(2l))
    1 + f(l) <= 1 + 1 + f(l + 1) <= 3 + f(l + 1) = 2 + f(2l + 2) = 1 + (1 + f(2l + 2))
    => f(k) = 1 + f(l) <= 1 + min(1 + f(2l), 1 + f(2l + 2)) = 1 + f(2l + 1) = 1 + f(k + 1).

    Proof of (*):

    1. If n % 4 = 3 and n != 3, denote n = 4k + 3 where k >= 1.
      f(n - 1) = f(4k + 2) = 1 + f(2k + 1) = 1 + min(f(2k) + 1, f(2k + 2) + 1) = min(f(2k) + 2, f(2k + 2) + 2)
      f(2k) + 2 = f(k) + 3 >= f(k + 1) + 2 = 1 + f(2k + 2)
      and f(2k + 2) + 2 > f(2k + 2) + 1, so f(n - 1) >= 1 + f(2k + 2) = f(4k + 4) = f(n + 1) => f(n) = min(f(n - 1) + 1, f(n + 1) + 1) = f(n + 1) + 1.

    2. If n = 3, it's obvious that f(3) = min(f(2) + 1, f(2) + 2) = f(2) + 1.

    3. If n % 4 = 1 and n > 1, denote n = 4k + 1 where k >= 1.
      f(n - 1) = f(4k) = 1 + f(2k)
      1 + f(2k) < 2 + f(2k)
      1 + f(2k) = 2 + f(k) <= 3 + f(k + 1) = 2 + f(2k + 2)
      => f(n - 1) = 1 + f(2k) <= min(2 + f(2k), 2 + f(2k + 2)) = 1 + min(f(2k) + 1, f(2k + 2) + 1) = 1 + f(2k + 1) = f(4k + 2) = f(n + 1)
      => f(n) = min(f(n - 1) + 1, f(n + 1) + 1) = f(n - 1) + 1.


  • -1
    O

    @bowendeng said in Python O(log n) time, O(1) space with explanation and proof:

    f(k) = f(2l)

    Why for even number the halve is best choice?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.