#5363. Tìm số duy nhất (Mã bài: SINGLENUM)

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho một mảng số nguyên a không rỗng, trong đó mỗi phần tử xuất hiện hai lần ngoại trừ một phần tử. Tìm phần tử duy nhất đó. Bạn phải triển khai một giải pháp có độ phức tạp thời gian tuyến tính và chỉ sử dụng không gian bộ nhớ hằng số.

Dữ liệu:

  • Dòng đầu chứa số nguyên dương n là số phần tử của mảng;
  • Dòng sau chứa n số nguyên a_1, a_2, \ldots, a_n .

Kết quả: Phần tử xuất hiện một lần duy nhất.

Ví dụ:

Dữ liệu:

5
4 1 2 1 2

Kết quả:

4

Giới hạn: 1 \le n \le 3 \cdot 10^4 ; -3 \cdot 10^4 \le a_i \le 3 \cdot 10^4 .