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:
Example 2:
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)
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)); } }
findOddOccurringElement()
method, which finds the element occurring an odd number of times using the solution described above.arr
.findOddOccurringElement()
method to find the odd occurring element in arr
.RELATED TAGS
CONTRIBUTOR
View all Courses