Algorithms: Solve 'Lonley Integer' Using Bit Manipulation

Key Takeaways

hi I'm Gail lock McDow author of crack and coding interview today I'm going to cover the lonely integer problem so suppose we have an array of integers and all the numbers appear twice except for one number that only appears once so how do we find that number the lonely integer well one way is using a hashmap so we can store all of the elements in a hash map and count how many times each character appears or each integer appears if something only appears once then that is of course the lonely integer but how can we reduce the space complexity even further we can't reduce the time complexity because well we have to touch every element anyway so how can we reduce the space complexity well let's think about these numbers in binary the reason why binary is a good bet here is that if we want to reduce a space complexity we're talk probably talking about constant space and that means we can't keep really any data structures so we don't have that much else to work with other than some sort of crazy bit issue so let's think about the bits here consider just that last bit there if every number appeared twice and literally every single number then we'd see an even number of ones if we don't see an even number of ones then so we' see an odd number of ones then that means that there's a one in that bit for the lonely integer so we could go through and actually count the number of ones another thing we could do is just exort everything because there's an even number of ones we'll wind up with a zero which means that the lonely integer has a zero but if there's an odd number of ones we'll wind up with a one so xoring all of those in this case will give us a one here now what about this next bit here well if we exort all of these again we're going to get a one and if we exort all of these here we're going to get a zero because we have an even number of ones and one xor one is zero and if we exor all of these again we have even number of ones we have two ones so we're going to get a zero here so what we can do actually rather than walking through this bit by bit by bit we can walk through our whole list exort all the values and interestingly that resulting value will be the lonely integer so implenting this is now almost trivial we just have some result which starts off at zero walk through each value in the my array and exort everything together and then just return my result so bit manipulation problems are often are one of those problems that do kind of involve AA moment sometimes so one tip off is if you're asked to keep the time complexity really really fast but still reduce the space complexity even more especially for like constant time that's sometimes where you're going to want some s bit manipulation approach the other tip is when you are tackling a bit manipulation problem try looking at it bit by bit rather than with all the integers at once and explore what the result of different operations like anding and xoring and shifting would give you so keep those things in mind and you know practice bit manipulation problems they aren't necessarily that hard once you get a hang of them once you get over the like intimidation Factor good luck