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 solution:

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));

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));

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 solution:

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));

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 solution:

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));