1. Tóm tắt đề bài

Cho số nguyên dương ~n~. Hãy đếm xem trong khoảng từ ~1~ đến ~n~ có bao nhiêu số không chứa chữ số ~4~ trong cấu trúc của chúng.

• Dữ liệu vào (Input):
  • Một dòng duy nhất chứa số nguyên dương ~n~ (~1 \le n \le 10^5~).
• Dữ liệu ra (Output):
  • Một số nguyên duy nhất là số lượng số tìm được thỏa mãn yêu cầu.

2. Phân tích bài toán & Giới hạn

• Giới hạn bài toán:

  • ~1 \le n \le 10^5~.
  • Số lượng số cần kiểm tra từ ~1~ đến ~n~ tối đa là ~10^5~ số.
  • Mỗi số nguyên ~x \le 10^5~ có tối đa ~6~ chữ số, do đó việc tách và kiểm tra từng chữ số của một số diễn ra trong tối đa ~6~ phép chia lấy dư.

• Đánh giá thời gian & Bộ nhớ:

  • Tổng số thao tác xử lý toàn bài tối đa chỉ khoảng ~10^5 \times 6 \approx 6 \times 10^5~ phép tính.
  • Máy tính xử lý được khoảng ~10^8~ phép tính/giây nên chương trình chạy hoàn toàn tức thì (~< 0.02~ giây), đảm bảo đạt điểm tối đa.
  • Giá trị ~n \le 10^5~ hoàn toàn nằm trong phạm vi kiểu số nguyên thông thường 32-bit (int).

3. Thuật toán xử lý

• Ý tưởng:

  1. Xây dựng hàm kiểm tra bool khongChua4(int x) để xác định xem số ~x~ có chứa chữ số 4 hay không:

     • Dùng vòng lặp while (x > 0) để kiểm tra lần lượt các chữ số từ phải qua trái.
     • Lấy chữ số tận cùng: int chu_so = x % 10;.
     • Nếu chu_so == 4: Phát hiện có chữ số 4 ~\rightarrow~ trả về false ngay lập tức.
     • Bỏ chữ số vừa xét: x /= 10;.
     • Nếu vòng lặp kết thúc mà không gặp chữ số 4 nào ~\rightarrow~ trả về true.

  2. Trong chương trình chính (main):

     • Khai báo biến n và biến đếm kết quả dem = 0.
     • Nhập số ~n~ từ bàn phím bằng lệnh chuẩn: cin >> n;.
     • Dùng vòng lặp for (int i = 1; i <= n; i++):
       • Nếu khongChua4(i) trả về true, tăng biến dem++.
     • Xuất kết quả dem ra màn hình và xuống dòng bằng cout << endl;.

• Độ phức tạp:

  • Thời gian: ~\mathcal{O}(n \cdot \log_{10}(n))~ — Duyệt qua tối đa ~10^5~ số, mỗi số kiểm tra tối đa 6 bước.
  • Không gian (bộ nhớ): ~\mathcal{O}(1)~ — Chỉ sử dụng các biến đơn lẻ.

4. Mã nguồn cài đặt (C++)

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

// Hàm kiểm tra một số có chứa chữ số 4 hay không
// Trả về true nếu KHÔNG chứa chữ số 4, ngược lại trả về false
bool khongChua4(int x) {
    while (x > 0) {
        int chu_so = x % 10;
        if (chu_so == 4) {
            return false;
        }
        x /= 10;
    }
    return true;
}

int main() {
    // Tối ưu nhập/xuất chuẩn
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int dem = 0;
    for (int i = 1; i <= n; i++) {
        if (khongChua4(i)) {
            dem++;
        }
    }

    cout << dem << endl;

    return 0;
}