400.Nth Digit

Tags: [num], [trick], [math]

Link: https://leetcode.com/problems/nth-digit/?tab=Description

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

Note:
nis 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.

Solution: num, math, trick

class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0:
            raise ValueError('the input is invalid')

        num_of_digits = 1
        step = 9
        seq_len = num_of_digits * step
        first = 1

        while n > seq_len:
            n -= seq_len
            num_of_digits += 1
            step *= 10
            seq_len = num_of_digits * step
            first *= 10

        target_num = first + (n - 1) / num_of_digits
        char_index = (n - 1) % num_of_digits

        return int(str(target_num)[char_index])

Revelation:

• [1...9] num_of_digits = 1, the sequence length = 1 * 9, the first elem = 10^(1 - 1) = 10^0 = 1
• [10...99] num_of_digits = 2, the sequence length = 2 * 90, the first elem = 10^(2 - 1) = 10^1 = 10
• [100...999] num_of_digits = 3, the sequence length = 3 * 900, the first elem = 10^(3 - 1) = 10^2 = 100
• [1000...9999] num_of_digits = 4, the sequence length = 4 * 9000, the first elem = 10^(4 - 1) = 10^3 = 1000
• [10000...99999] num_of_digits = 5, the sequence length = 5 * 90000, the first elem = 10^(5 - 1) = 10^4 = 10000
• How to understand the way to get the target_num, and char_index?

Note:

• Time complexity = O(lg(num)), num is the given number.
• A number n will have at most O(lg(n)) digits

Time Limited Exceeded

class Solution(object):
    def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0:
            raise ValueError('the input is invalid')

        num_of_digits = 1
        seq_base_len = 9
        seq_len = 1 * seq_base_len

        while seq_len < n:
            num_of_digits += 1
            seq_base_len = 9
            for _ in xrange(num_of_digits - 1):
                seq_base_len *= 10

            seq_len += num_of_digits * seq_base_len

        prev_seq_len = 0
        for d in xrange(1, num_of_digits):
            seq_base_len = 9
            for _ in xrange(d - 1):
                seq_base_len *= 10

            prev_seq_len += d * seq_base_len

        n -= prev_seq_len

        base = 1
        for _ in xrange(num_of_digits - 1):
            base *= 10

        seq = []
        for _ in xrange(n):
            seq += list(str(base))
            base += 1

        return int(seq[n - 1])

Note:

• Time complexity = O(?)