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

• ``````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

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