Python in O(log n) beats 90% of the solutions


  • 0
    N
    class Solution(object):
        def findNthDigit(self, n):
            curr, prev = 10, 1
            for i in range(1, 32):
    
                if (n >= i * (curr - prev)):
    # Decrese the no of digits found in previous powers
                    n -= i * (curr - prev)    
            # Just increment the current power of 10  
                    prev = curr
                    curr *= 10
                else:
        # Apply a binary search in ( prev, curr)
                    mid = (curr + prev) // 2
                    while (prev < curr - 1):
                        note = (mid - prev) * i
                        if (note > n):
                            curr = mid
                        else:
                            n -= note
                            prev = mid
                        mid = (curr + prev) // 2
    
                    mid += n // i
                    n = n % i
                    if (n == 0):
                        return (mid - 1) % 10
                    else:
                        n = i + 1 - n
                        while (n > 1):
                            mid //= 10
                            n -= 1
                        return mid % 10
    

    Keep incrementing the power of ten until you find the onces b/w which the answer lies, by decreasing the digits found in previous (prev, curr) range.

    When such an power is found apply a binary search in (prev, curr) to find the required number
    And then you can easily find the required digit in < 10 operations


Log in to reply
 

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