Chữ Số Thứ N Trong C++

Giả sử chúng ta có một dãy số nguyên vô hạn, chúng ta phải tìm chữ số thứ n của dãy này. Ví dụ: n = 11 → đầu ra 0 vì dãy 123456789101112... chữ số thứ 11 là 0.

Để giải quyết, chúng ta làm theo các bước:

len := 1, cnt := 9, start := 1.
Khi n > len * cnt: n -= len * cnt; cnt *= 10; start *= 10; len++.
start += (n - 1) / len.
s := start dưới dạng chuỗi.
Trả về s[(n - 1) % len] - '0'.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

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

class Solution {
public:
    int findNthDigit(int n) {
        lli len = 1;
        lli cnt = 9;
        lli start = 1;
        while(n > len * cnt){
            n -= len * cnt;
            cnt *= 10;
            start *= 10;
            len++;
        }
        start += (n - 1) / len;
        string s = to_string(start);
        return s[(n - 1) % len] - '0';
    }
};

int main(){
    Solution ob;
    cout << (ob.findNthDigit(11));
}

Chữ Số Thứ N Trong C++

Ví dụ (C++)

Đầu vào

Đầu ra