Hiểu bài toán

Bài toán yêu cầu tính trung bình cộng của các số lẻ trong một mảng một chiều gồm n số nguyên. Đầu vào là số lượng phần tử n và mảng A gồm n số nguyên. Đầu ra là một số thực được làm tròn đến chữ số thập phân thứ 4, là giá trị trung bình của các phần tử lẻ. Nếu mảng không có phần tử lẻ nào, cần xử lý để không chia cho 0 (giá trị mặc định là 0).

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

Cách Duyệt mảng và tính tổng (Cơ bản)

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    long long sum = 0; // Dùng long long để tránh tràn số nếu tổng lớn
    int cnt = 0;

    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        // Kiểm tra số lẻ: số không chia hết cho 2
        if (a[i] % 2 != 0) {
            sum += a[i];
            cnt++;
        }
    }

    if (cnt == 0) {
        printf("0");
    } else {
        printf("%.4lf", (double)sum / cnt);
    }

    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Đây là cách tiếp cận trực tiếp nhất. Chúng ta duyệt qua từng phần tử của mảng. Nếu phần tử đó là số lẻ (dùng phép chia lấy dư % 2 != 0), ta cộng dồn vào biến tổng sum và tăng biến đếm cnt. Cuối cùng, thực hiện phép chia sum / cnt và in ra với độ chính xác 4 chữ số thập phân. Cần kiểm tra trường hợp cnt == 0 để tránh lỗi chia cho 0.

Cách Tối ưu bộ nhớ (Không lưu mảng)

#include <stdio.h>
#include <math.h>

int main() {
    int n;
    scanf("%d", &n);
    long long sum = 0;
    int cnt = 0;
    int val;

    for (int i = 0; i < n; i++) {
        scanf("%d", &val);
        // Dùng abs(val) để xử lý số âm (ví dụ -3 % 2 ở một số hệ thống trả về -1)
        // Tuy nhiên, với C99 trở lên, -3 % 2 là -1 (khác 0) nên vẫn đúng, nhưng abs an toàn hơn.
        if (abs(val) % 2 == 1) {
            sum += val;
            cnt++;
        }
    }

    if (cnt == 0) {
        printf("0");
        return 0;
    }

    // In ra số thực với 4 số lẻ thập phân
    printf("%.4lf", 1.0 * sum / cnt);

    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Phương pháp này cải thiện về mặt bộ nhớ. Thay vì tạo một mảng int a[n] để lưu tất cả các số, ta chỉ cần một biến tạm val để đọc từng số từ input. Nếu số đó là số lẻ, ta cập nhật ngay vào sum và cnt. Điều này giảm bộ nhớ cần thiết từ O(n) xuống O(1). Việc dùng abs(val) để kiểm tra tính chẵn/lẻ giúp xử lý chính xác các số âm.

Cách Phân tách hàm (Modular)

#include <stdio.h>

float average(int a[], int n) {
    long long sum = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] % 2 != 0) {
            sum += a[i];
            cnt++;
        }
    }
    // Nếu cnt = 0, phép chia 0 sẽ trả về kết quả không xác định,
    // nhưng trong ngữ cảnh bài toán, ta cần in 0. Code này cần cải thiện phần này.
    return (float)sum / cnt;
}

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    int cnt = 0;
    for(int i=0; i<n; i++) if(a[i]%2!=0) cnt++;

    if(cnt == 0) printf("0");
    else printf("%.4f", average(a, n));

    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Cách tiếp cận này có cấu trúc mã nguồn tốt hơn bằng cách tách logic tính toán trung bình ra một hàm riêng average. Điều này giúp mã nguồn dễ đọc và dễ bảo trì hơn. Tuy nhiên, về bản chất thuật toán vẫn là duyệt mảng và tính tổng. Lưu ý rằng giải pháp gốc của người dùng (Solution 3) có thể bị lỗi runtime nếu mảng rỗng (không có số lẻ) vì return (float)sum/cnt sẽ chia cho 0 và in ra nan hoặc inf thay vì 0. Do đó, cần xử lý cnt==0 ở hàm main trước khi gọi hàm.

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

Bài học kinh nghiệm

• Phép chia lấy dư % 2 là cách nhanh nhất để kiểm tra số chẵn/lẻ. Tuy nhiên, đối với số âm, cần chú ý đến cách tính của ngôn ngữ (ví dụ: -3 % 2 ở một số ngôn ngữ là -1 chứ không phải 1). Sử dụng abs(x) % 2 == 1 hoặc x % 2 != 0 là cách an toàn.
• Kiểu dữ liệu lưu tổng nên là long long thay vì int để tránh tràn số (overflow) khi tổng các phần tử vượt quá giới hạn của kiểu int (dù n ≤ 1000 và |A| ≤ 10^6, tổng tối đa có thể lên tới 10^9, vẫn nằm trong giới hạn int 32-bit nhưng long long an toàn hơn).
• Để in ra số thực với 4 chữ số thập phân, sử dụng format string %.4lf (trong C) hoặc %.4f.

Lỗi thường gặp

• Quên xử lý trường hợp mảng không có số lẻ nào (cnt = 0). Khi đó, phép chia sum / cnt sẽ gây lỗi chia cho 0 hoặc kết quả không xác định (NaN). Cần in ra 0 trong trường hợp này.
• Sai kiểu dữ liệu khi in ra: Dùng printf("%d", sum / cnt) sẽ làm tròn xuống số nguyên, sai yêu cầu bài toán. Phải dùng printf("%.4lf", (double)sum / cnt).
• Dùng biến đếm hoặc tổng sai kiểu (ví dụ dùng int cho sum trong khi tổng có thể lớn) mặc dù trong bài này giới hạn đầu vào cho phép dùng int nhưng long long là thói quen tốt.