400.md

400. Nth Digit

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

Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Example 1:

Input:
3

Output:
3
Example 2:

Input:
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.

my thoughts:

1. there are 9 one digit (9), 90 two digits (180), 900 three digits (2700).... so 9*i*(10**(i-1)) then track which digit of which num we are looking for.

my solution:

**********32ms
class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 10:
            return n
        i = 1
        digits = 0
        while digits<n:
            digits += 9*i*(10**(i-1))
            i += 1
        i -= 1
        digits -= 9*i*(10**(i-1))
        print digits, i
        count = (n - digits)/i if (n-digits)%i == 0 else (n-digits)/i + 1
        num = 10**(i-1) + count -1
        d = i if (n-digits)%i == 0 else (n-digits)%i
        res = str(num)[d-1]
        print count, num, d, res
        return int(res)

my comments:

from other ppl's solution:

1. neater implementation, 25ms:
class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        width = 1
        while n > 9 * 10 **(width-1) * width:
            n -= 9 * 10 ** (width-1) * width
            width += 1
        return int(str(10**(width-1) + (n-1)//width)[(n-1)%width])