Editorial for evensum: Tính tổng các số ở vị trí chẵn

Hiểu bài toán

Bài toán yêu cầu tính tổng các số nguyên nằm ở vị trí chẵn trong một dãy số. Dãy số có N phần tử, được nhập từ bàn phím. Quy ước: vị trí chẵn là các vị trí 2, 4, 6,... (tính theo thứ tự 1-based). Ví dụ, với dãy [1, 2, -1, 3, 4] (N=5), các số ở vị trí chẵn là 2 (vị trí 2) và 3 (vị trí 4), tổng của chúng là 5.

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

Cách Lưu trữ mảng và duyệt

#include <stdio.h>
#include <limits.h>
#include <math.h>
#include <string.h>
#define Nmax 100006
int main()
{
    int n,a[Nmax],sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=2;i<=n;i+=2) sum+=a[i];
    printf("%d",sum);
    return 0;
}

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

Cách tiếp cận này sử dụng một mảng cố định (a[Nmax]) hoặc mảng động để lưu trữ toàn bộ dãy số. Chương trình đọc N, sau đó sử dụng một vòng lặp để đọc N số vào mảng. Sau đó, một vòng lặp khác chạy từ chỉ số 2 đến N với bước nhảy là 2 (i += 2) để cộng dồn các số ở vị trí chẵn vào biến tổng. Vì mảng trong C bắt đầu từ chỉ số 0, nhưng đề bài dùng quy ước 1-based, tác giả đã khéo léo lưu số vào a[1], a[2]... để chỉ số mảng khớp với vị trí đề bài, hoặc đơn giản là chỉ cần lặp từ 2 đến N.

Cách Xử lý trực tiếp (Không lưu mảng)

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    long long sum = 0;
    int num;

    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        if (i % 2 != 0) {
            sum += num;
        }
    }

    printf("%lld\n", sum);
    return 0;
}

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

Đây là cách tiếp cận tối ưu hơn. Thay vì lưu toàn bộ dãy số vào mảng, ta chỉ cần dùng một biến num để đọc từng số trong vòng lặp. Biến i đếm số thứ tự của phần tử đang đọc (bắt đầu từ 0). Nếu i là số lẻ (tức i % 2 != 0), nó tương ứng với vị trí chẵn trong dãy (vì vị trí 2 tương ứng với chỉ số 1, vị trí 4 tương ứng với chỉ số 3...). Ta chỉ cần cộng giá trị đó vào tổng. Biến sum nên khai báo kiểu long long để tránh tràn số nếu tổng các số quá lớn.

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

Bài học kinh nghiệm

• Sự chênh lệch giữa quy ước 1-based (đề bài) và 0-based (mảng trong C/C++): Vị trí chẵn (2, 4, 6...) tương ứng với chỉ số mảng lẻ (1, 3, 5...).
• Không cần thiết phải lưu trữ toàn bộ dãy số trong bộ nhớ để giải quyết bài toán này, giúp tiết kiệm bộ nhớ đáng kể (từ O(N) xuống O(1)).

Lỗi thường gặp

• Lỗi tràn số lũy kế (Integer Overflow): Nếu N lớn (lên tới 10^5) và mỗi số có giá trị tới 10^5, tổng có thể lên tới 10^10, vượt quá giới hạn của kiểu int (khoảng 2*10^9). Cần dùng long long cho biến tổng.
• Nhầm lẫn giữa chỉ số mảng và vị trí: Vòng lặp for(int i=1; i<=n; i+=2) chỉ đúng nếu mảng được khai báo và dùng start từ 1. Nếu dùng start từ 0, công thức phải là for(int i=1; i<n; i+=2) hoặc kiểm tra i%2 == 1.