LC-0400 Medium LeetCode

400. Nth Digit

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 36% Topics: Math, Binary Search

Reading material

Math & Geometry 12 min Binary Search 12 min

Reference solution (spoiler · python)

# Time:  O(logn)
# Space: O(1)

class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        digit_len = 1
        while n > digit_len * 9 * (10 ** (digit_len-1)):
            n -= digit_len  * 9 * (10 ** (digit_len-1))
            digit_len += 1

        num = 10 ** (digit_len-1) + (n-1)/digit_len

        nth_digit = num / (10 ** ((digit_len-1) - ((n-1)%digit_len)))
        nth_digit %= 10

        return nth_digit

Solution from kamyu104/LeetCode-Solutions · MIT