Nth Digit ใน C++ : หาตัวเลขหลักที่ N ในลำดับจำนวนเต็มต่อเนื่อง

ให้ลำดับจำนวนเต็มต่อเนื่อง: "1234567891011121314..." หา **Digit ตำแหน่งที่ n** (1-indexed)

ตัวอย่าง

n = 11

Sequence: 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 ...

Index: 1 2 3 4 5 6 7 8 9 10 11

Digit 11 คือ 0 (ของเลข 10)

แนวทาง: Digit Length Groups (Mathematical)

จัดกลุ่มตามจำนวนหลัก (Digit Length):

• 1-digit: 1-9 -> 9 ตัว * 1 หลัก = 9 Digits
• 2-digit: 10-99 -> 90 ตัว * 2 หลัก = 180 Digits
• 3-digit: 100-999 -> 900 ตัว * 3 หลัก = 2700 Digits
• ...

1. หา Group (Length len) ที่ n อยู่: ลบ len * count ทีละ Group จน n <= len * count
2. หา **ตัวเลขจริง** ที่ chứa Digit นั้น: start + (n-1) / len
3. หา **Index ในตัวเลข**: (n-1) % len

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

class Solution {
public:
    int findNthDigit(int n) {
        lli len = 1;      // Digit length
        lli cnt = 9;      // Count of numbers in this length
        lli start = 1;    // First number in this length

        // 1. Find the length group
        while (n > len * cnt) {
            n -= len * cnt;
            cnt *= 10;
            start *= 10;
            len++;
        }

        // 2. Find the actual number
        start += (n - 1) / len;

        // 3. Extract the specific digit
        string s = to_string(start);
        return s[(n - 1) % len] - '0';
    }
};

Input / Output

Input:  11
Output: 0

ความซับซ้อน (Complexity)

• Time: O(log₁₀ N) — จำนวน Group = จำนวนหลักของ N
• Space: O(log₁₀ N) — String ของตัวเลขเป้าหมาย

จุดสำคัญ

• ใช้ long long ป้องกัน Overflow ตอนคูณ cnt *= 10
• Index Math: (n-1) / len = Offset จาก Start, (n-1) % len = Digit Index ในตัวเลข
• ไม่ต้อง Generate String ยาวๆ คำนวณทางคณิตศาสตร์ตรงไปตรงมา

Math-based Solution ที่มีประสิทธิภาพสูงครับ