Exceptionally Odd

Problem

Given an array of N positive integers where all numbers occur even number of times except one number which occurs odd number of times. Find the exceptional number.

Examples:

Example 1:

Input:
N = 7
Arr[] = {1, 2, 3, 2, 3, 1, 3}
Output: 3
Explaination: 3 occurs three times.

Example 2:

Input:
N = 7
Arr[] = {5, 7, 2, 7, 5, 2, 5}
Output: 5
Explaination: 5 occurs three times.

Your task:

You don't need to read input or print anything. Your task is to complete the function getOddOccurrence() which takes arr[] and n as input parameters and returns the exceptional number.

• Expected Time Complexity: $O(N)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=N<=10^5$
• $1<=arr[i]<=10^6$

Solution

Python

def getOddOccurrence(self, arr, n):
    result = 0
    for num in arr:
        result ^= num
    return result 

Java

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

C++

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

C

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

• Time Complexity: $O(N)$
• Auxiliary Space: $O(1)$