text: /**
   * @param {number[]} nums
   * @return {number}
   */
  const findDuplicate = function(nums) {
    const len = nums.length
    if(len > 0) {
      let slow = nums[0]
      let fast = nums[nums[0]]
      while(slow !== fast) {
        slow = nums[slow]
        fast = nums[nums[fast]]
      }
      slow = 0
      while(slow !== fast) {
        slow = nums[slow]
        fast = nums[fast]
      }
      return slow
    }
    return -1;
  };
  
  // another
  
  /**
   * @param {number[]} nums
   * @return {number}
   */
  const findDuplicate = function(nums) {
    let n = nums.length - 1,
      res = 0
    for (let p = 0; p < 32; ++p) {
      let bit = 1 << p,
        a = 0,
        b = 0
      for (let i = 0; i <= n; ++i) {
        if (i > 0 && (i & bit) > 0) ++a
        if ((nums[i] & bit) > 0) ++b
      }
      if (b > a) res += bit
    }
    return res
  }
  
  // another
  
  /**
   * @param {number[]} nums
   * @return {number}
   */
  const findDuplicate = function(nums) {
    const hash = {};
    for (let i = 0; i < nums.length; i++) {
      if (hash.hasOwnProperty(nums[i])) {
        return nums[i];
      } else {
        hash[nums[i]] = 1;
      }
    }
  };
  
  
  /**
  
  # File: FindDuplicate.py
  # Author: Keith Schwarz (htiek@cs.stanford.edu)
  #
  # An algorithm for solving the following (classic) hard interview problem:
  #
  # "You are given an array of integers of length n, where each element ranges
  #  from 0 to n - 2, inclusive.  Prove that at least one  duplicate element must
  #  exist, and give an O(n)-time, O(1)-space algorithm for finding some
  #  duplicated element.  You must not modify the array elements during this 
  #  process."
  #
  # This problem (reportedly) took CS legend Don Knuth twenty-four hours to solve
  # and I have only met one person (Keith Amling) who could solve it in less time
  # than this.
  #
  # The first part of this problem - proving that at least one duplicate element
  # must exist - is a straightforward application of the pigeonhole principle.
  # If the values range from 0 to n - 2, inclusive, then there are only n - 1
  # different values.  If we have an array of n elements, one must necessarily be
  # duplicated.
  #
  # The second part of this problem - finding the duplicated element subject to
  # the given constraints - is much harder.  To solve this, we're going to need a
  # series of nonobvious insights that transform the problem into an instance of
  # something entirely different.
  #
  # The main trick we need to use to solve this problem is to notice that because
  # we have an array of n elements ranging from 0 to n - 2, we can think of the
  # array as defining a function f from the set {0, 1, ..., n - 1} onto itself.
  # This function is defined by f(i) = A[i].  Given this setup, a duplicated
  # value corresponds to a pair of indices i != j such that f(i) = f(j).  Our
  # challenge, therefore, is to find this pair (i, j).  Once we have it, we can
  # easily find the duplicated value by just picking f(i) = A[i].
  #
  # But how are we to find this repeated value?  It turns out that this is a
  # well-studied problem in computer science called cycle detection.  The general
  # form of the problem is as follows.  We are given a function f.  Define the
  # sequence x_i as
  #
  #    x_0     = k       (for some k)
  #    x_1     = f(x_0)
  #    x_2     = f(f(x_0))
  #    ...
  #    x_{n+1} = f(x_n)
  #
  # Assuming that f maps from a domain into itself, this function will have one
  # of three forms.  First, if the domain is infinite, then the sequence could be
  # infinitely long and nonrepeating.  For example, the function f(n) = n + 1 on
  # the integers has this property - no number is ever duplicated.  Second, the
  # sequence could be a closed loop, which means that there is some i so that
  # x_0 = x_i.  In this case, the sequence cycles through some fixed set of
  # values indefinitely.  Finally, the sequence could be "rho-shaped."  In this
  # case, the sequence looks something like this:
  #
  #     x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
  #                        ^                       |
  #                        |                       |
  #                        +-----------------------+
  #
  # That is, the sequence begins with a chain of elements that enters a cycle,
  # then cycles around indefinitely.  We'll denote the first element of the cycle
  # that is reached in the sequence the "entry" of the cycle.
  #
  # For our particular problem of finding a duplicated element in the array,
  # consider the sequence formed by starting at position n - 1 and then
  # repeatedly applying f.  That is, we start at the last position in the array,
  # then go to the indicated index, repeating this process.  My claim is that
  # this sequence is rho-shaped.  To see this, note that it must contains a cycle
  # because the array is finite and after visiting n elements, we necessarily
  # must visit some element twice.  This is true no matter where we start off in
  # the array.  Moreover, note that since the array elements range from 0 to
  # n - 2 inclusive, there is no array index that contains n - 1 as a value.
  # Consequently, when we leave index n - 1 after applying the function f one
  # time, we can never get back there.  This means that n - 1 can't be part of a
  # cycle, but if we follow indices starting there we must eventually hit some
  # other node twice.  The concatenation of the chain starting at n - 1 with the
  # cycle it hits must be rho-shaped.
  #
  # Moreover, think about the node we encounter that starts at the entry of the
  # cycle.  Since this node is at the entry of the cycle, there must be two
  # inputs to the function f that both result in that index being generated.  For
  # this to be possible, it must be that there are indices i != j with
  # f(i) = f(j), meaning that A[i] = A[j].  Thus the index of the entry of the
  # cycle must be one of the values that is duplicated in the array.
  #
  # There is a famous algorithm due to Robert Floyd that, given a rho-shaped
  # sequence, finds the entry point of the cycle in linear time and using only
  # constant space.  This algorithm is often referred to as the "tortoise and
  # hare" algorithm, for reasons that will become clearer shortly.
  #
  # The idea behind the algorithm is to define two quantities.  First, let c be
  # the length of the chain that enters the cycle, and let l be the length of the
  # cycle.  Next, let l' be the smallest multiple of l that's larger than c.
  # I claim that for any rho-shaped sequence l' defined above, that
  #
  #    x_{l'} = x_{2l'}
  #
  # The proof is actually straightforward and very illustrative - it's one of my
  # favorite proofs in computer science.  The idea is that since l' is at least
  # c, it must be contained in the cycle.  Moreover, since l' is a multiple of
  # the length of the loop, we can write it as ml for some constant m.  If we
  # start at position x_{l'}, which is inside the loop, then take l' more steps
  # forward to get to x_{2l'}, then we will just walk around the loop m times,
  # ending up right back where we started.
  #
  # One key trick of Floyd's algorithm is that even if we don't explicitly know l
  # or c, we can still find the value l' in O(l') time.  The idea is as follows.
  # We begin by keeping track of two values "slow" and "fast," both starting at
  # x_0.  We then iteratively compute
  #
  #    slow = f(slow)
  #    fast = f(f(fast))
  #
  # We repeat this process until we find that slow and fast are equal to one
  # another.  When this happens, we know that slow = x_j for some j, and
  # fast = x_{2j} for that same j.  Since x_j = x_{2j}, we know that j must be at
  # least c, since it has to be contained in the cycle.  Moreover, we know that j
  # must be a multiple of l, since the fact that x_j = x_{2j} means that taking j
  # steps while in the cycle ends up producing the same result.  Finally, j must
  # be the smallest multiple of l greater than c, since if there were a smaller
  # multiple of l greater than c then we would have reached that multiple before
  # we reached j.  Consequently, we must have that j = l', meaning that we can
  # find l' without knowing anything about the length or shape of the cycle!
  #
  # To complete the construction, we need to show how to use our information
  # about l' to find the entry to the cycle (which is at position x_c).  To do
  # this, we start off one final variable, which we call "finder," at x_0.  We
  # then iteratively repeat the following:
  #
  #   finder = f(finder)
  #   slow   = f(slow)
  #
  # until finder = slow.  We claim that (1) the two will eventually hit each
  # other, and (2) they will hit each other at the entry to the cycle.  To see
  # this, we remark that since slow is at position x_{l'}, if we take c steps
  # forward, then we have that slow will be at position x_{l' + c}.  Since l' is
  # a multiple of the loop length, this is equivalent to taking c steps forward,
  # then walking around the loop some number of times back to where you started.
  # In other words, x_{l' + c} = x_c.  Moreover, consider the position of the
  # finder variable after c steps.  It starts at x_0, so after c steps it will be
  # at position x_c.  This proves both (1) and (2), since we've shown that the
  # two must eventually hit each other, and when they do they hit at position x_c
  # at the entry to the cycle.
  #
  # The beauty of this algorithm is that it uses only O(1) external memory to
  # keep track of two different pointers - the slow pointer, and then the fast
  # pointer (for the first half) and the finder pointer (for the second half).
  # But on top of that, it runs in O(n) time.  To see this, note that the time
  # required for the slow pointer to hit the fast pointer is O(l').  Since l' is
  # the smallest multiple of l greater than c, we have two cases to consider.
  # First, if l > c, then this is l.  Otherwise, if l < c, then we have that
  # there must be some multiple of l between c and 2c.  To see this, note that
  # in the range c and 2c there are c different values, and since l < c at least
  # one of them must be equal to 0 mod l.  Finally, the time required to find the
  # start of the cycle from this point is O(c).  This gives a total runtime of at
  # most O(c + max{l, 2c}).  All of these values are at most n, so this algorithm
  # runs in time O(n).
  
  def findArrayDuplicate(array):
      assert len(array) > 0
  
      # The "tortoise and hare" step.  We start at the end of the array and try
      # to find an intersection point in the cycle.
      slow = len(array) - 1
      fast = len(array) - 1
  
      # Keep advancing 'slow' by one step and 'fast' by two steps until they
      # meet inside the loop.
      while True:
          slow = array[slow]
          fast = array[array[fast]]
  
          if slow == fast:
              break
  
      # Start up another pointer from the end of the array and march it forward
      # until it hits the pointer inside the array.
      finder = len(array) - 1
      while True:
          slow   = array[slow]
          finder = array[finder]
  
          # If the two hit, the intersection index is the duplicate element.
          if slow == finder:
              return slow
  
  
  */
  