Trusted answers to developer questions
Trusted Answers to Developer Questions

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
RELATED COURSES

View all Courses

Keep Exploring