Hiểu bài toán

Bài toán yêu cầu tìm chữ số thứ K của một dãy vô hạn được tạo ra bằng cách nối liên tục các số tự nhiên tăng dần (1, 2, 3, ...). Ví dụ, dãy bắt đầu là '123456789101112...'. Với K lên tới 10^9, chúng ta không thể xây dựng dãy này trong bộ nhớ. Thay vào đó, cần tìm quy luật về độ dài của các nhóm số (1 chữ số, 2 chữ số, ...) để xác định số chứa chữ số K, và sau đó tìm chính xác chữ số đó trong số đó.

Các cách tiếp cận

Cách Quy hoạch theo nhóm số (Đếm và Trừ)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long k;
    while (cin >> k) {
        long long len = 1, count = 9, start = 1;

        // Bước 1: Xác định nhóm số (1 chữ số, 2 chữ số, ...)
        while (k > len * count) {
            k -= len * count;
            len++;
            count *= 10;
            start *= 10;
        }

        // Bước 2: Tìm số cụ thể trong nhóm
        start += (k - 1) / len;
        string s = to_string(start);

        // Bước 3: Tìm chữ số trong số đó
        cout << s[(k - 1) % len] << "\n";
    }
    return 0;
}

• Time Complexity: O(log K) - Vòng lặp chạy tối đa 10 lần (vì K <= 10^9, số có tối đa 10 chữ số)
• Space Complexity: O(1) - Chỉ sử dụng biến số

Cách tiếp cận này chia dãy thành các nhóm: các số 1 chữ số (9 số, tổng 9 ký tự), các số 2 chữ số (90 số, tổng 180 ký tự), v.v. Ta lặp qua các nhóm, trừ đi độ dài của nhóm đó từ K cho đến khi K nằm trong phạm vi của nhóm hiện tại. Giả sử K đang nằm trong nhóm có độ dài len và bắt đầu từ số start. Số chứa chữ số thứ K là số thứ (k - 1) / len (tính từ 0) trong nhóm này, tức là start + (k - 1) / len. Chữ số cần tìm là chữ số thứ (k - 1) % len của số đó (tính từ trái sang phải, bắt đầu từ 0).

Cách Thay đổi biến đếm (Phân tích biến số)

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

char findKthDigit(long long k) {
    long long len = 1;
    long long count = 9; 
    long long start = 1; 

    long long used = 0; 
    while (k > used + len * count) {
        used += len * count;
        len++;
        count *= 10;
        start *= 10;
    }

    long long num = start + (k - used - 1) / len;

    long long pos = (k - used - 1) % len;

    string numStr = to_string(num);
    return numStr[pos];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long k;
    while (cin >> k) {
        cout << findKthDigit(k) << endl;
    }

    return 0;
}

• Time Complexity: O(log K)
• Space Complexity: O(1)

Cách này tương tự cách 1 nhưng logic vòng lặp và tính toán chỉ số được biến đổi một chút. Thay vì trực tiếp trừ vào K, ta dùng biến used để lưu tổng số ký tự của các nhóm đã đi qua. Vòng lặp dừng lại khi k nằm trong khoảng (used, used + len * count]. Số tìm được tính theo công thức start + (k - used - 1) / len. Đây chỉ là một cách viết khác của cùng một thuật toán, giúp minh họa rõ hơn việc 'bỏ qua' các ký tự trước đó.

Cách Định nghĩa hàm và chuyển đổi chuỗi

#include <iostream>
#include <cmath>
using namespace std;

char findDigit(long long K) {
    long long n = 1; // Số chữ số
    long long count = 9; // Số lượng số có n chữ số
    long long start = 1; // Số đầu tiên có n chữ số

    // Bước 1: Xác định số chữ số n của số chứa chữ số thứ K
    while (K > n * count) {
        K -= n * count;
        n++;
        count *= 10;
        start *= 10;
    }

    // Bước 2: Tìm số cụ thể chứa chữ số thứ K
    long long number = start + (K - 1) / n;

    // Bước 3: Tìm chữ số cụ thể trong số đó
    int digitPos = (K - 1) % n;
    return to_string(number)[digitPos];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int X;
    long long K;
    while (cin >> K) {
        cout << findDigit(K) << '\n';
    }

    return 0;
}

• Time Complexity: O(log K)
• Space Complexity: O(1) - (Chuỗi số tạo ra có độ dài tối đa 10)

Đây là biến thể phổ biến của thuật toán. Hàm findDigit thực hiện việc xác định nhóm số và số chứa chữ số K. Việc quan trọng là công thức tính số: start + (K - 1) / n. Ví dụ, nếu K đang ở nhóm 2 chữ số (n=2), start=10. Nếu K còn lại là 1 hoặc 2, (K-1)/2 = 0 => số 10. Nếu K còn lại là 3 hoặc 4, (K-1)/2 = 1 => số 11. Sau đó, dùng to_string để chuyển số thành chuỗi và truy cập phần tử tại chỉ số (K-1) % n.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Phân loại các số theo số chữ số (1 chữ số, 2 chữ số, ...) để chia dãy thành các khối có độ dài tính được.
• Công thức tính số chứa chữ số K: Số_bắt_đầu_của_nhóm + (K - 1) / số_chữ_số_của_nhóm.
• Công thức tìm vị trí chữ số trong số đó: (K - 1) % số_chữ_số_của_nhóm.

Lỗi thường gặp

• Sử dụng biến kiểu int hoặc long thay vì long long trong C++ có thể gây tràn số (overflow) khi K gần 10^9, vì các biến phụ trợ như len * count có thể vượt quá 2^31.
• Nhầm lẫn giữa việc đếm từ 0 và đếm từ 1 khi tính chỉ số chuỗi. Phép trừ 1 ở công thức (k - 1) là bắt buộc.
• Quên cập nhật biến start hoặc count sau mỗi vòng lặp trong khi tính toán nhóm số.