Hiểu bài toán

Bài toán yêu cầu tìm số thứ N trong dãy số tự nhiên chỉ chứa các chữ số 4 và 7, được sắp xếp theo thứ tự tăng dần. Ví dụ, dãy sẽ bắt đầu như sau: 4, 7, 44, 47, 74, 77, ... Với mỗi testcase, input là số nguyên N, output là số thứ N tương ứng trong dãy.

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

Cách Sinh dãy bằng BFS/Queue (Precompute)

#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;

const int MAX_N = 1000000; // Kích thước tối đa cần thiết
vector<string> lucky;

void precompute() {
    queue<string> q;
    q.push("4");
    q.push("7");
    while (lucky.size() < MAX_N) {
        string s = q.front();
        q.pop();
        lucky.push_back(s);
        q.push(s + "4");
        q.push(s + "7");
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precompute();
    int t;
    if (cin >> t) {
        while (t--) {
            int n;
            cin >> n;
            cout << lucky[n-1] << "\n";
        }
    }
    return 0;
}

• Time Complexity: O(N) để sinh dãy (với N là max query), O(1) để trả lời mỗi câu h hỏi.
• Space Complexity: O(N) để lưu dãy.

Phương pháp này sử dụng hàng đợi (queue) để sinh ra các số may mắn theo thứ tự. Bắt đầu với "4" và "7", ta liên tục lấy số đầu hàng đợi, thêm vào danh sách, và đẩy hai số mới tạo bằng cách nối "4" và "7" vào đuôi. Cách này đảm bảo thứ tự tăng dần (vì hàng đợi FIFO). Ta có thể precompute trước một lượng lớn số (ví dụ 1000 hoặc 1 triệu) để trả lời truy vấn nhanh.

Cách Quy luật Bitmask (Phân tích số học)

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

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

    int T;
    cin >> T;
    while (T--) {
        long long N;
        cin >> N;

        long long cnt = 0;
        long long len = 1;

        // Tìm độ dài của số thứ N
        while (true) {
            long long soLuong = (1LL << len); // 2^len
            if (cnt + soLuong >= N) break;
            cnt += soLuong;
            len++;
        }

        // Tính chỉ số (index) của số đó trong nhóm có độ dài 'len'
        // index chạy từ 0 đến 2^len - 1
        long long index = N - cnt - 1;

        string result = "";
        // Duyệt từng bit của index để构建 số
        for (long long i = 0; i < len; i++) {
            if (index & (1LL << i)) 
                result = "7" + result;
            else 
                result = "4" + result;
        }

        cout << result << "\n";
    }
    return 0;
}

• Time Complexity: O(log N) cho mỗi truy vấn (vì số lượng chữ số tối đa là log2(N)).
• Space Complexity: O(1) (không cần mảng lớn).

Các số may mắn có thể được ánh xạ tương ứng với số tự nhiên trong hệ nhị phân.

• Độ dài 1: 4 (0), 7 (1) -> 2 số
• Độ dài 2: 44 (00), 47 (01), 74 (10), 77 (11) -> 4 số
• Độ dài k: 2^k số. Ta xác định độ dài d của số thứ N bằng cách trừ đi số lượng các số có độ dài nhỏ hơn. Sau đó, số thứ N là số thứ (N - tổngsốđộdàinhỏ_hơn) trong dãy các số có độ dài d. Nếu coi 4 là bit 0 và 7 là bit 1, thì số đó chính là biểu diễn nhị phân của chỉ số này (trong phạm vi d bit), được viết bằng các ký tự 4 và 7.

Cách Sinh dãy bằng số học (Dùng hàng đợi số nguyên)

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

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

    int T;
    cin >> T;

    vector<long long> queries(T);
    long long maxN = 0;
    for (int i = 0; i < T; i++) {
        cin >> queries[i];
        maxN = max(maxN, queries[i]);
    }

    // Sinh dãy 4,7 theo giá trị tăng dần
    vector<long long> arr;
    arr.reserve(maxN);
    queue<long long> q;
    q.push(4);
    q.push(7);

    while ((long long)arr.size() < maxN) {
        long long x = q.front(); 
        q.pop();
        arr.push_back(x);
        q.push(x * 10 + 4);
        q.push(x * 10 + 7);
    }

    for (long long n : queries)
        cout << arr[n - 1] << "\n";

    return 0;
}

• Time Complexity: O(N_max) để precompute.
• Space Complexity: O(N_max).

Tương tự Approach 1 nhưng sử dụng số nguyên thay cho chuỗi. Các số được sinh ra bằng cách nhân 10 và cộng 4 hoặc 7. Do hàng đợi ưu tiên (queue) FIFO, các số sẽ được sinh ra theo đúng thứ tự tăng dần. Đây là cách sinh chuẩn xác nhất về mặt giá trị số học.

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

Bài học kinh nghiệm

• Dãy số may mắn có tính chất 'tầng lớp': các số có độ dài k nhỏ hơn tất cả các số có độ dài k+1.
• Có thể ánh xạ trực tiếp chỉ số N vào hệ nhị phân để tạo ra số may mắn tương ứng mà không cần sinh toàn bộ.
• Bài toán này là một dạng của 'BFS trên cây' hoặc 'Sinh xâu theo thứ tự từ điển'.

Lỗi thường gặp

• Sử dụng số nguyên 32-bit (int) khi N lớn hoặc khi tính toán số lượng số (2^len), dẫn đến tràn số. Phải dùng kiểu long long (64-bit).
• Truy cập ngoài biên mảng nếu precompute không đủ số lượng (ví dụ N=1000 nhưng chỉ sinh 999 số).
• Lỗi logic khi tính chỉ số index (off-by-one error) trong phương pháp bitmask.