LeetCode: Single Number II
Hey all.
Link to the problem: https://leetcode.com/problems/single-number-ii/description/
Picture of the problem included in case you don't want to use the link.
I am hoping that someone explains to me what this algorithm does and why does it solve the problem?
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
let ones = 0;
let twos = 0;
for (let num of nums) {
ones = (ones ^ num) & ~twos;
twos = (twos ^ num) & ~ones;
}
return ones; }; I have googled these operators and learned that those are bit arithemtic operations that are being done, like AND, OR, XOR and similar, but I still have no idea what the idea behind this solution is and I would like to learn it. Thanks a lot.
return ones; }; I have googled these operators and learned that those are bit arithemtic operations that are being done, like AND, OR, XOR and similar, but I still have no idea what the idea behind this solution is and I would like to learn it. Thanks a lot.
1 Reply
How did you even found this solution? 😄
I can't pretend to understand what's happening but after throwing a console log inside the iteration, and reading some of the documentation, it seems that it basically "cancels out" the individual bits composing the duplicated numbers.
I think having exactly three numbers is key, as by doing it just once it flips the bits only to get a different number; the second flip of the bits should return the original number and a final third flip of bits will again remove it. Somehow after all this, the final flip using the "single number" will yield the correct result... I don't have the slightest idea how anyone would come up with this sort of code. But my guess is that this is a sort of "elimination game" where each flip of bits simply results in cancelling duplicate numbers, although I don't think this will work with 4 and perhaps even 5 repetitions; 3 is the key.