Find duplicate in linear time and space

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) :
);
return ret;
};

console.log(findDuplicate(lst));


My imperative solutions:

function findDuplicate2(lst) {
const set = new Set();
let i = 0;
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));

• (How about sketching an O(1) space solution?) Apr 10, 2019 at 8:16
• @greybeard isn't findDuplicate3 O(1) space? I don't use an additional variable - only the running variable i. Apr 10, 2019 at 8:22
• Announced as imperative solution, I didn't expect nor notice more than one - even eye-balling it has to wait till after "day-time chores". Apr 10, 2019 at 8:49
• @greybeard but I don't know whether it's good practice to mutate the input value. Apr 10, 2019 at 8:50
• sorry for nitpicking, but a set – by definition – is a collection of distinct objects. Apr 10, 2019 at 10:47

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

• Hmm.... wait a minute. The task says the elements in the array are members of the set of natural numbers {1..n}. But it doesn't say that the elements consists of consecutive numbers from 1 to n. For example this could also be a valid input: const lst = [1, 3, 4,7,8,7]  Apr 10, 2019 at 9:15
• @thadeuszlay the "set {1, 2, ..., n}." means all values from 1 to and including n else it would be a subset of the set "set {1, 2, ..., n}." which contains some of the values. If array length is n + 1 then the array must contain the set {1,2,..., n} Apr 10, 2019 at 10:41
• I see. What is your opinion about this solution: const findDuplicate = arr => arr.reduce((acc, x) => acc + x, 0) - ((arr.length - 1)*(arr.length) / 2 ); Apr 10, 2019 at 15:24
• One downside of your algorithm is that it runs till the end of the array even though it may have come across the duplicate already. Apr 10, 2019 at 15:30
• @thadeuszlay I assume that the items are not in order, that means that worst case will always requires stepping over all items. Your (comment) reduce version is just as valid Apr 10, 2019 at 15:59

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(