Related Tags

bit operations

# How to find the number occurring an odd number of times

Ravi

## Overview

How do we find a number that occurs an odd number of times from a list of positive integers? We also know that all numbers occur an even number of times.

Example 1:

• Input: lst - [1, 1, 2, 4, 3, 5, 7, 1, 2, 3, 4, 1, 7]
• Output: 5

Example 2:

• Input: lst - [10]
• Output: 10

### Solution

The intuition here is to use bitwise XOR on all the list elements. This method works because:

• XOR of a number with itself results in zero that is n ^ n = 0

• XOR of a number with zero results in the number, that is n ^ 0 = n.

• Cumulative property of XOR that is being ^ n = n ^ m

• Time Complexity - O(n)

• Space Complexity - O(1)

### Code

Let’s view a code example.

class Main{

static int findOddOccurringElement(int[] arr) {
if(arr.length == 0) return -1;
int xor = arr[0];
for(int i=1; i< arr.length;i++)
xor = xor ^ arr[i];

return xor;
}

public static void main(String[] args) {
int[] arr = {1, 1, 2, 4, 3, 5, 7, 1, 2, 3, 4, 1, 7};
System.out.println("The odd occurring element is " + findOddOccurringElement(arr));
}
}

Try it out!

### Explanation

• Lines 3–10: We define the findOddOccurringElement() method, which finds the element occurring an odd number of times using the solution described above.
• Line 13: We define an Array arr.
• Line 14: We define the findOddOccurringElement() method to find the odd occurring element in arr`.

RELATED TAGS

bit operations

CONTRIBUTOR

Ravi
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time