singleNumber-leetcode.js

/**
Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
**/

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
  /**
    Since all numbers in nums appears three times except for one,
    we need to track numbers which have appeared only once or twice.

    One way to do this is to count this number of times a particular
    bit has appeared so far. For example, if we have a nums array
    with values:

    110
    011
    001

    We can say that the bit counts are {1, 2, 2} corresponding with the
    first, second, and third digits respectively.
    
    If a bit appears 3 times, we need to reset it's bit count back
    to zero, because we only care about tracking bits that have appeared
    in a number not divisible by 3. Since the question states that the
    number that does not occur three times only occurs once, we're really
    only looking for bits whose:

    number of occurrences % 3 == 1

    The bits of the "ones" variable represents digits whose occurrences % 3 == 1
    The bits of the "twos" variable represents digits whose occurrences % 3 == 2
    The bits of the "threes" variable represents digits whose occurrences % 3 == 0
  **/
  var ones = 0
  var twos = 0
  var threes = 0

  var twosAndThrees, onesAndThrees, newTwos
  for (var i = 0; i < nums.length; i++) {
    /**
      newTwos represents bits that were not previously 1 in "twos"
      but now need to be 1 in "twos" after considering the current number
      in the array.

      If a bit appears in "ones" as well as the current number, then it
      needs to be bumped up from ones to twos.

      Therefore "ones & current number" represents bits that have occurred
      twice
    **/
    newTwos = ones & nums[i]

    /**
      "twosAndThrees" represents the previous "twos" merged with "newTwos".

      We cannot use this number as the new "twos" just yet, because we have
      still not accounted for bits that were previously twos but should now
      be in "threes". This number therefore contains bits that should be in
      "twos" as well as "threes". Hence the name "twosAndThrees"
    **/
    twosAndThrees = twos | newTwos

    /**
      Like "twosAndThrees", "onesAndThrees" contains bits that should be in
      "ones" as well as "threes".

      XORing "ones" and "nums[i]" does two things:

      1. Changes bits that were previously 1 to 0 if they are in both. If a
         bit appears in both "ones" and the new number, then it's occurrences % 3
         is now 2 instead of one. Basically, these are numbers that were previously
         "ones" but are now "twos".

      2. Changes bits that were previously 0 to one if they are in "nums[i]" but not
         "ones". This adds to "ones" all bits that were previously not in "ones" but
         now should be.

      In these two steps, we've accounted for 1) "ones" that should now be "twos" and
      2) new "ones". But this number might still have "threes", because the bits added
      in step 2 could be new "ones" as well as new "threes".
    **/
    onesAndThrees = ones ^ nums[i]

    /**
      Since "twosAndThrees" and "onesAndThrees" both contain "threes" as well as "ones"
      and "twos", their intersection should represent "threes" since a bit cannot be in
      both in "ones" as well as "twos"
    **/
    threes = twosAndThrees & onesAndThrees

    /**
      Removing the "threes" bits in "twosAndThrees" and "onesAndThrees" gives you the new
      "ones" and "twos".
    **/
    twos = twosAndThrees & ~threes
    ones = onesAndThrees & ~threes
  }

  return ones // "Find that single one" - the outstanding number should appear only once
};