How to find the number occurring an odd number of times
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));}}
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 inarr.
TRENDING TOPICS
