Đếm số chẵn trong dãy

Nguồn: CLUE OJ Độ khó: Dễ Mảng 1 chiều Phép chia lấy dư

Đề bài

Cho số nguyên dương $N$ và dãy số nguyên $A_1, A_2, \ldots, A_N$. Hãy đếm số lượng số chẵn có trong dãy $A$ (số $0$ và các số âm chia hết cho $2$ cũng là số chẵn).

Dữ liệu vào:

• Dòng đầu là số nguyên dương $N$.
• Dòng thứ hai gồm $N$ số nguyên $A_1, A_2, \ldots, A_N$.

Kết quả:

In ra số lượng số chẵn đếm được.

Giới hạn:

• $1 \le N < 10000$
• $|A_i| < 10^{18}$

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

5
1 12 4 -3 8

Ví dụ 1 – output

3

Các số chẵn là $12, 4, 8$.

Nguồn: phỏng theo bài "MẢNG 5.5" – vinhdinhcoder.net (chủ đề Mảng 1 chiều).

Lời mở đầu

Bài đếm cơ bản nhất với mảng: đếm số chẵn. Dễ nhưng vẫn có bẫy với số âm: trong C++, -3 % 2 bằng -1 chứ không phải 1.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởnga % 2 == 0Lời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau.

Test	Nội dung kiểm tra
1	Ví dụ của đề (có số lẻ âm $-3$)
2–3, 6	$N = 1$ với số 0, số lẻ; dãy có số 0 – bỏ qua số 0 là sai
4–5, 10, 12–14, 19	Số lẻ âm – đếm số lẻ bằng a % 2 == 1 rồi lấy $N$ trừ đi là sai
7–8, 11–12, 15, 17–18, 20	Giá trị cỡ $10^{18}$, quanh $2^{32}$ – int và double sai
9, 16	Toàn số chẵn, dãy cỡ $10^9$

Ý tưởngSố chẵn ⇔ chia 2 dư 0

Duyệt mảng, phần tử nào có a[i] % 2 == 0 thì tăng biến đếm. Điều kiện này đúng với mọi số chẵn: dương, âm và cả số 0.

Số dư của số âm trong C++

C++ chia lấy dư giữ dấu của số bị chia: -3 % 2 == -1, -4 % 2 == 0. Vì vậy kiểm tra số lẻ bằng a % 2 == 1 sẽ bỏ sót số lẻ âm – nên kiểm tra số chẵn trực tiếp bằng == 0, hoặc số lẻ bằng != 0.

Em nhập dãy rồi bấm Tiếp:

Dãy A =

Ví dụ nhanh:

Lời giảiĐếm bằng phép chia lấy dư

Mảng kiểu long long vì $|A_i| < 10^{18}$.

C++▶ Chạy tay từng dòng codeĐếm các phần tử chia 2 dư 0.

Dữ liệu vào (stdin) – sửa thoải mái5 1 12 4 -3 8

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Python luôn trả số dư không âm (-3 % 2 == 1) nên không gặp bẫy này, nhưng viết x % 2 == 0 vẫn là cách rõ ràng nhất.
2. Số 0 là số chẵn (0 % 2 == 0).

Không gian$O(N)$

Thời gian$O(N)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.008s. Bản Python đúng 20/20 test, chạy lâu nhất 0.019s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Đếm số lẻ bằng a % 2 == 1 rồi lấy $N$ trừ đi	8/20	sai test 1, 4, 7, 8, 10, 11, 12, 13, 14, 16, 19, 20
Dùng int	12/20	sai test 7, 8, 11, 12, 15, 17, 18, 20
Không đếm số 0	16/20	sai test 2, 6, 13, 19
Dùng double và fmod	15/20	sai test 7, 11, 12, 18, 20

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.008s	Full điểm
	Python	20/20	0.019s	Full điểm
n − số lẻ	C++	8/20	–	Mất 12 test
Dùng int	C++	12/20	–	Mất 8 test
Bỏ số 0	C++	16/20	–	Mất 4 test
Dùng double	C++	15/20	–	Mất 5 test

Ghi chú của mình: trong C++, đừng bao giờ kiểm tra số lẻ bằng x % 2 == 1 khi $x$ có thể âm – dùng x % 2 != 0.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇