A different O(lgn) way in Python


  • 1
    S

    **Edit: The time complexity is O(lgn)^2), not O(lgn)

    Instead of binary search, we can use the trick we used when solving Pow(x, n)

    class Solution(object):
        def firstBadVersion(self, n):
            """
            :type n: int
            :rtype: int
            """
            i = 0
            while not (not isBadVersion(i) and isBadVersion(i+1)):
                plus = 1
                while i+plus <=n and not isBadVersion(i+plus):
                    i+=plus
                    plus*=2
            return i + 1
    

  • 0

    This isn't O(lgn) but O((logn)2). For example think of n=1014 and 1014 being the first bad version. You'll first add 1+2+4+8+16+32+64+128+256, then you'll add 1+2+4+8+16+32+64+128, then you'll add 1+2+4+8+16+32+64, and so on.

    Btw, what's up with the account upvoting your topics being called "symgates2"?


  • 0
    S

    @StefanPochmann You are right, thanks for the example. It is lg(n) + lg(n/2) + lg(n/4) ... 1. Which is O(lgn)^2) in total.


Log in to reply
 

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