Kiểm tra IQ chẵn lẻ

Nguồn: CLUE OJ Độ khó: Dễ Mảng 1 chiều Chẵn lẻ Số âm

Đề bài

Tèo đang chuẩn bị làm bài kiểm tra IQ. Dạng câu hỏi hay gặp nhất là: trong $N$ số cho trước, tìm một số khác với các số còn lại. Tèo nhận thấy số đó luôn khác các số còn lại về tính chẵn lẻ: hoặc chỉ có đúng một số chẵn (các số còn lại lẻ), hoặc chỉ có đúng một số lẻ (các số còn lại chẵn).

Em hãy giúp Tèo viết chương trình tìm số khác loại đó.

Dữ liệu vào:

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

Kết quả:

In ra giá trị của số khác loại.

Giới hạn:

• $3 \le N \le 99$
• $|A_i| < 10^{18}$ (có thể có số âm)
• Dữ liệu đảm bảo có đúng một số khác các số còn lại về tính chẵn lẻ.

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

4
4 2 3 8

Ví dụ 1 – output

3

Ví dụ 2 – input

3
-3 2 4

Ví dụ 2 – output

-3

• Ví dụ 1: chỉ có $3$ là số lẻ.
• Ví dụ 2: chỉ có $-3$ là số lẻ (số âm cũng có tính chẵn lẻ như bình thường).

Nguồn: phỏng theo bài "KIỂM TRA IQ" – vinhdinhcoder.net (chủ đề Mảng 1 chiều).

Lời mở đầu

Trong dãy chỉ có đúng một số "lạc loài" về chẵn lẻ. Đếm số chẵn là biết số lạc loài là chẵn hay lẻ, rồi duyệt lại để tìm nó. Bẫy thú vị: số âm trong C++ có -3 % 2 = -1 chứ không phải 1. Ghi chú: đề gốc chỉ nói "in ra số khác loại", ví dụ $4\ 2\ 3\ 8 \to 3$ trùng cả giá trị lẫn vị trí (số 3 ở vị trí thứ 3) nên không phân biệt được; mình chốt in giá trị và thêm ví dụ thứ hai. Ràng buộc gốc $0 < n$ nhưng với $n \le 2$ không xác định được số khác loại, nên mình chốt $3 \le n \le 99$.

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ưởngđếm số chẵnLờ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. Mọi test có $3 \le N \le 99$, $|A_i| < 10^{18}$.

Test	Nội dung kiểm tra
1–2	Hai ví dụ của đề
3–9	Dãy ngắn, số 0, số khác loại ở đầu / giữa / cuối
6–7, 10, 12–13, 17–18	Số lẻ âm – bắt lỗi kiểm tra a % 2 == 1
10–18, 20	Số vượt int (tới $10^{18}$, quanh $2^{31}, 2^{32}$)
3, 8, 11	Hai số đầu khác loại nhau

Ý tưởngĐếm số chẵn trước, tìm sau

Bước 1: đếm số lượng số chẵn soChan. Nếu soChan == 1 thì số khác loại là số chẵn duy nhất; ngược lại số khác loại là số lẻ duy nhất.

Bước 2: duyệt lại mảng, in số đầu tiên có tính chẵn lẻ cần tìm.

Kiểm tra chẵn lẻ với số âm

C++ lấy dư giữ dấu số bị chia: -3 % 2 == -1. Viết a % 2 == 1 để kiểm tra số lẻ sẽ coi $-3$ là số chẵn! Hãy viết a % 2 == 0 (chẵn) hoặc a % 2 != 0 (lẻ) – đúng với cả số âm.

Em nhập dữ liệu rồi bấm Tiếp để xem chương trình duyệt mảng từng bước:

a =

Ví dụ nhanh:

Lời giảiĐếm chẵn rồi duyệt tìm

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

C++▶ Chạy tay từng dòng codeĐếm số chẵn, rồi tìm số khác loại.

Dữ liệu vào (stdin) – sửa thoải mái4 4 2 3 8

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Không cần kiểm tra trường hợp "không tìm thấy" vì đề đảm bảo luôn có đúng một số khác loại.
2. Python lấy dư theo kiểu toán học (-3 % 2 == 1) nên không gặp bẫy này, nhưng viết % 2 == 0 vẫn là thói quen tốt.

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.002s. Bản Python đúng 20/20 test, chạy lâu nhất 0.022s. 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ú
Kiểm tra số lẻ bằng a[i] % 2 == 1	13/20	sai test 6, 7, 10, 12, 13, 17, 18
In vị trí thay vì giá trị	2/20	sai test 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Đọc vào int	10/20	sai test 10, 11, 12, 13, 14, 15, 16, 17, 18, 20
Chỉ nhìn 2 số đầu để đoán loại cần tìm	17/20	sai test 3, 8, 11

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.002s	Full điểm
	Python	20/20	0.022s	Full điểm
% 2 == 1	C++	13/20	–	Mất 7 test
In vị trí	C++	2/20	–	Mất 18 test
Dùng int	C++	10/20	–	Mất 10 test
Đoán từ 2 số đầu	C++	17/20	–	Mất 3 test

Ghi chú của mình: với số âm, phép % trong C++ cho số dư âm. Kiểm tra chẵn lẻ hãy so với 0: x % 2 == 0 / 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 😇