Số xuất hiện số lần lẻ

Hãy nhớ lại thử thách bạn đã giải trong bài học "Toán tử XOR", trong đó chúng ta đã dùng các tính chất của XOR. Câu hỏi chúng ta sẽ giải trong bài học này khá giống với thử thách đó. Vậy, bài toán chúng ta sẽ tìm hiểu là:

Tìm phần tử xuất hiện số lần lẻ trong mảng đã cho.

Bạn sẽ được cho một mảng chứa một số phần tử số nguyên. Trong số các phần tử đó, tất cả các phần tử khác đều xuất hiện số lần chẵn, ngoại trừ một phần tử.

Giả sử ta có mảng int Arr[11] = { 2, 5, 6, 6, 6, 4, 5, 2, 5, 4, 5}.

Trong mảng này,

• '2' xuất hiện hai lần (chẵn).
• '5' xuất hiện bốn lần (chẵn).
• '6' xuất hiện ba lần (lẻ).
• '4' xuất hiện hai lần (chẵn).

Vậy ở đây, số '6' xuất hiện số lần lẻ. Và đó là số chúng ta cần tìm trong bài toán, tức là số xuất hiện số lần lẻ trong mảng.

Như đã thấy trong bài học về toán tử "XOR", với một số 'x',

• x ⊕ x = 0 (trong đó ký hiệu '⊕' biểu thị phép toán XOR)
• x ⊕ 0 = x

Vậy, khi dùng tính chất thứ nhất, XOR các phần tử xuất hiện số lần chẵn sẽ cho kết quả 0. Sau đó, dùng tính chất thứ hai, ta sẽ còn lại số xuất hiện số lần lẻ.

Về cơ bản, XOR tất cả các phần tử trong mảng sẽ cho ta kết quả. Vậy là xong, đó chính là lời giải cho bài toán. Dễ phải không?

Độ phức tạp thời gian của bài toán này là O(n), vì ta phải duyệt toàn bộ mảng và XOR tất cả các phần tử.