Find duplicate in linear time and space

Question

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 => {
  const set = new Set();
  let ret;
  lst.some(x => 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 < len; i++) {
    if (lst[Math.abs(lst[i])] >= 0)  {
      lst[Math.abs(lst[i])] = -lst[Math.abs(lst[i])];
    } else {
      return Math.abs(lst[i]);
    }
  }
}

console.log(findDuplicate3(lst));

Answer 1

You know all the values in the array before you start.

The solution you are looking for is purely is a mathematical one.

The set is 1 to n, thus all items in the set sum to sum = 1 + 2 + 3 + ... + n

Thus if there is a duplicate in an array a that contains the set of 1 to a.length then that duplicate must be the sum of all values subtract the sum of the unique values.

function findDuplicate(arr) {
    var sum = 0, sumArr = 0, i = arr.length;
    while (i--) { 
        sum += i;
        sumArr += arr[i];
    }
    return sumArr - sum;
}

or

function findDuplicate(arr) {
    var res = 0, i = arr.length;
    while (i--) { res += i - arr[i] }
    return -res;
}

Answer 2

I'm not a big fan of the functional solution for following reasons:

1. 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.

2. 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 => {
  const set = new Set();
  return lst.find(
    x => set.has(x) || !set.add(x)
  );
};

However I do admit it may be a bit cryptic.