Find duplicate in linear time and space The task:


  You are given an array of length n + 1 whose elements belong to the
  set {1, 2, ..., n}. By the pigeonhole principle, there must be a
  duplicate. Find it in linear time and space.


const lst = [1,2,3,4,5,6,7,8,7];


My functional solution:

const findDuplicate = lst =&gt; {
  const set = new Set();
  let ret;
  lst.some(x =&gt; set.has(x) ?
           !Boolean(ret = x) :
           !Boolean(set.add(x))
  );
  return ret;
};

console.log(findDuplicate(lst));


My imperative solutions:

function findDuplicate2(lst) {
  const set = new Set();
  let i = 0;
  while(!set.has(lst[i])) { set.add(lst[i++]); }
  return lst[i];
}

console.log(findDuplicate2(lst));

function findDuplicate3(lst) {
  for (let i = 0, len = lst.length; i &lt; len; i++) {
    if (lst[Math.abs(lst[i])] &gt;= 0)  {
      lst[Math.abs(lst[i])] = -lst[Math.abs(lst[i])];
    } else {
      return Math.abs(lst[i]);
    }
  }
}

console.log(findDuplicate3(lst));
I'm not a big fan of the functional solution for following reasons:


the pointless use of the some() method, because its callback always returns false. This is this possibly an error? The call would short-circuit, if Boolean(ret = x) weren't negated. But even then some() would be the wrong choice, because it's just used for short-circuiting. I believe find() would be a better choice.
the conditional expression together with Boolean(...) expressions are a bit if a crutch. The conditional expression seems to be only used to be shorter that an full if, but that requires Boolean(), so that it still returns a boolean value needed for some().


Using find() I've come up with

const findDuplicate = lst =&gt; {
  const set = new Set();
  return lst.find(
    x =&gt; set.has(x) || !set.add(x)
  );
};


However I do admit it may be a bit cryptic.