Hi, I'm Gayle Laakmann McDowell, author of Cracking the 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 the elements in a hashmap and count how many
times each character appears, or each integer appears, and 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
the space complexity we're probably talking about constant space and
that means we can't keep really any data structures 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 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 XOR
everything, because if 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 1. So XORing all of those in this case will give us a 1 here. Now what
about this next bit here? Well if we explore all of these again
we're going to get a 1 and if we XOR all of these here we're going to get a 0
because have an even number of ones and 1 XOR with 1 is 0. And if we XOR all of
these, again, if we have an even number of ones, we have two 1s, so we're going to get a 0 here. So what
we can do actually, rather than walking through this bit by bit by bit, we can walk
through our whole list, XOR all the values and interestingly that resulting value will be the lonely integer. So
implementing this is now almost trivial. We just have some result which starts off at
zero, walk through each value in my array, and XOR everything together.
And then just return my result. So bit manipulation problems are often, are one
of those problems that do kind of involve aha moments 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 like for constant time, that
sometimes where you're going to want some 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.
