Friday, November 9, 2012

Single non-repeating number


Given an array of numbers where every number except one is repeated, efficiently find the number.
for e.g. {9, 1, 8, 7, 8, 1, 9}
Answer: 7

Approach
Sorting and finding each number with the next number - this is not an ideal approach as it takes O(N^2).
Instead use bit manipulation. XOR all numbers and the left out number is the result

Solution

No comments:

Post a Comment

UA-36403895-1