Odd Occurring Element - C++ Solution

1. Introduction

This blog post addresses an interesting array processing problem: finding the element that appears an odd number of times in an array where all other elements appear an even number of times. The solution is to be found in linear time without using extra memory, demonstrating the power of bitwise operations in C++.

Problem

Given an integer array where all elements appear an even number of times except one that appears an odd number of times, the task is to find that odd occurring element.

Example:

Input: [4, 3, 6, 2, 6, 4, 2, 3, 4, 3, 3]

Output: 4

2. Solution Steps

1. Initialize a variable, say result, to 0.

2. Iterate through the array.

3. Use the XOR operator on each element with result.

4. Since XOR of two same numbers is 0 and XOR of a number with 0 is the number itself, the final value of result will be the odd occurring element.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to find the odd occurring element
int findOddOccurring(const vector<int>& nums) {
    int result = 0;

    // XOR all the elements
    for (int num : nums) {
        result ^= num;
    }

    return result;
}

int main() {
    vector<int> nums = {4, 3, 6, 2, 6, 4, 2, 3, 4, 3, 3};
    cout << "Odd occurring element: " << findOddOccurring(nums) << endl;
    return 0;
}

Output:

Odd occurring element: 4

Explanation:

The findOddOccurring function uses the XOR operator to find the odd occurring element. It iterates through the array, applying XOR between each element and a running result variable. Due to the properties of XOR, all elements that appear an even number of times will cancel each other out, leaving only the odd occurring element in the result. This approach is efficient, running in linear time and not requiring any additional memory.