Introduction

Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.

Input : arr = {1, 2, 3, 2, 3, 1, 3}
Output : 3

Approach

The approach that comes to the mind is to perform XOR operation on the elements.

Code

//User function Template for Java

class Solution {
    int getOddOccurrence(int[] arr, int n) {
        // code here
        int result = 0;
        for (int a : arr) {
            result = a ^ result;
        }
        return result;
    }
}

References