Given an unsorted array that contains even number of occurrences for all numbers except two numbers. Find the two numbers which have odd occurrences in O(n) time complexity and O(1) extra space.
Solution:
XOR of all no.s which occur even no. of times is zero, so XOR of two odd numbers will be the output. Choose a bit at which they differ, and then XOR all elements which have that bit set to '1' gives one no.
similarly find the other number.
http://www.geeksforgeeks.org/archives/19378
Solution:
XOR of all no.s which occur even no. of times is zero, so XOR of two odd numbers will be the output. Choose a bit at which they differ, and then XOR all elements which have that bit set to '1' gives one no.
similarly find the other number.
http://www.geeksforgeeks.org/archives/19378
No comments:
Post a Comment