400.md

400 Nth Digit

Description

link

---

Solution

observation: 假设我们要找第2886 个位 (就target数 是998，target bit 是8)

• 2886 - 9 - 9 * 10 * 2 = 2697 < 91010*3 = 2700
• target 就落在了区域3中( 100- 999 )，因为这个区域中每一位都有3位，所以可以计算target
• target 数是以 100 为起始数，(2697 - 1)/3 = 898 为100以后的数，-1是因为起始数本来就算一个数，不能重复计算
• target 数 = 100 + 898 = 998
• (2697-1) % 3 = 2 就是 998 的target bit
• target bit = 998.charAt( 2 ) = 8;

---

Code

class Solution:
    def findNthDigit(self, n: int) -> int:
        start = 1
        base = 9
        digits = 1
        
        # step 1 find how many digits the number need
        while n > base * digits:
            n -= base * digits
            digits += 1
            base *= 10
            start *= 10
        
        # step 2 find what number we need
        target = start + (n - 1) // digits
        reminder = (n - 1) % digits
        
        # step 3 find which digit we need
        return int(str(target)[reminder])