Nth Digit Python Solution with Tests

Tested Python solution for LeetCode 400 with 29 pytest cases. Generate a practice environment with lcpy.

LeetCode 400, Medium. Topics: Math, Binary Search. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 29 parametrized pytest cases, and a playground notebook:

lcpy gen -n 400   # by problem number
lcpy gen -s nth_digit   # by problem name

​

Problem

Given an integer n, return the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ....

​

Examples

Input: n = 3
Output: 3

Input: n = 11
Output: 0

Explanation: The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … is a 0, which is part of the number 10.

​

Constraints

• 1 <= n <= 2^31 - 1

Follow up: Could you find the nth digit without using extra memory?

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(log n)
    # Space: O(1)
    def find_nth_digit(self, n: int) -> int:
        digits = 1
        count = 9
        start = 1
        while n > digits * count:
            n -= digits * count
            digits += 1
            count *= 10
            start *= 10
        num = start + (n - 1) // digits
        return int(str(num)[(n - 1) % digits])

​

Complexity

Time	Space
O(log n)	O(1)

​

Tags