Short Problem Definition:
Find value that occurs in odd number of elements.
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1)
This problem can be found in many algorithm books. A xor A cancels itself and B xor 0 is B. Therefore A xor A xor B xor C xor C is B.
def solution(A): missing_int = 0 for value in A: missing_int ^= value return missing_int
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.