Tìm số thứ N chỉ chứa các chữ số lẻ bằng C++

Tìm số tự nhiên thứ N mà tất cả các chữ số đều là lẻ (1, 3, 5, 7, 9). Ví dụ: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 31, 33, ...

Phân tích quy luật

Các số chỉ chứa chữ số lẻ có quy luật:

• 1 chữ số: 1, 3, 5, 7, 9 (5 số)
• 2 chữ số: 11, 13, 15, 17, 19, 31, 33, ... (5² = 25 số)
• 3 chữ số: 111, 113, ... (5³ = 125 số)

Mã nguồn C++

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

int main() {
    queue<int> q;
    int cnt = 0, ans = 0;
    int n;
    cin >> n;
    int a[5] = {1, 3, 5, 7, 9};

    for (int i = 0; i < 5; i++) {
        cnt++;
        if (cnt == n) ans = a[i];
        q.push(a[i]);
    }
    if (ans) {
        cout << ans << "\n";
    } else {
        while (true) {
            int x = q.front(); q.pop();
            for (int j = 0; j < 5; j++) {
                int temp = x * 10 + a[j];
                q.push(temp);
                cnt++;
                if (cnt == n) {
                    ans = temp;
                    break;
                }
            }
            if (ans) break;
        }
        cout << ans << "\n";
    }
    return 0;
}

Kết quả

9

(Input 5 → Output 9)

Giải thích

1. Khởi tạo queue với 5 số lẻ 1 chữ số.
2. Đếm đến khi cnt == n.
3. Nếu chưa đủ, BFS: lấy số đầu queue, sinh 5 số mới bằng x*10 + digit, đẩy vào queue, tiếp tục đếm.

Độ phức tạp O(N), không gian O(N) do queue.

Kết luận

Bài viết trình bày thuật toán BFS tìm số thứ N chỉ chứa chữ số lẻ. Mã C++ sử dụng queue, dễ hiểu và hiệu quả. Có thể triển khai bằng C, Java, Python.