# 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?) – greybeard Apr 10 '19 at 8:16
• @greybeard isn't findDuplicate3 O(1) space? I don't use an additional variable - only the running variable i. – thadeuszlay Apr 10 '19 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". – greybeard Apr 10 '19 at 8:49
• @greybeard but I don't know whether it's good practice to mutate the input value. – thadeuszlay Apr 10 '19 at 8:50
• sorry for nitpicking, but a set – by definition – is a collection of distinct objects. – morbusg Apr 10 '19 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]  – thadeuszlay Apr 10 '19 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} – Blindman67 Apr 10 '19 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 ); – thadeuszlay Apr 10 '19 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. – thadeuszlay Apr 10 '19 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 – Blindman67 Apr 10 '19 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(