Single Number Problem Walkthrough
Given an array arr[] of positive integers where every element appears even times except for one. Find that number occurring an odd number of times.
Input: arr = [1, 1, 2, 2, 2]
Output: 2
All elements appear twice except 2, which appears three times.
Input: arr = [8, 8, 7, 7, 6, 6, 1]
Output: 1
All elements appear twice except 1, which appears once.
class Solution {
public:
// Function to find the element in the array which occurs only once.
int getSingle(vector<int>& arr) {
for (int i = 0; i < arr.size(); i++) {
int count = 0;
for (int j = 0; j < arr.size(); j++) {
if (arr[i] == arr[j]) count++;
}
if (count % 2 != 0) return arr[i];
}
return -1;
}
};Optimal idea: XOR cancels out pairs. XOR of all numbers leaves the odd-occurring element.
// O(n), O(1) space
int getSingleXOR(const vector<int>& arr) {
int x = 0;
for (int v : arr) x ^= v;
return x;
}