Given an array containing integers, where each number occurs three times except for one number which occurs only once, find the number which occurs only once.
Couldnt think of a way to use XOR for this. XOR works fine when all numbers appear twice and only one of them appears once.
But we can still use some bit magic for this question.
Lets consider ith bit of all numbers. If we count the total number of one's in the ith bit for all numbers and later divide this number by 3, we can get the ith bit of the desired number. So lets say if we have total of 7 elements for eg: {10, 13, 10, 13, 10, 4, 13}. Now if we count total number of ones for LSB in the whole array, we will get 3(for 3 13s, for every other number LSB is 0). Now if we find remainder of the count when divided by 3, we will get the LSB of the desired number. Why? Because every other number appears three times, hence all other ones will appear three times and when taking a remainder will cancel out.
Read full article from Code Arena: Find single number!!
No comments:
Post a Comment