Tìm phần tử đơn lẻ trong mảng 2n+1 số nguyên trong C++

Trong bài toán này, cho mảng gồm (2n + 1) số nguyên. Trong đó n phần tử xuất hiện 2 lần, chỉ có 1 phần tử xuất hiện 1 lần. Nhiệm vụ là tìm phần tử đơn lẻ đó.

Ví dụ minh họa:

Đầu vào

arr[] = {1, 3, 5, 6, 5, 1, 3}

Đầu ra

5

Phương pháp giải

Cách đơn giản: dùng bộ đếm tần suất. Cách hiệu quả: dùng XOR. XOR tất cả phần tử. XOR hai số bằng nhau = 0. XOR với 0 = số đó. Kết quả là phần tử xuất hiện 1 lần.

Chương trình minh họa:

Ví dụ

#include <iostream> 
using namespace std; 

int findSingleValue(int arr[], int n) { 
    int element = 0; 
    for (int i = 0; i < n; i++) 
        element = element ^ arr[i]; 
    return element; 
} 

int main() { 
    int arr[] = { 1, 3, 5, 6, 5, 1, 3 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout<<"The element of the array with single occurrence is "<<findSingleValue(arr, n); 
    return 0; 
}

Kết quả

The element of the array with single occurrence is 6