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

• greybeard: (How about sketching an O(1) space solution?)
• thadeuszlay: @greybeard isn't findDuplicate3 O(1) space? I don't use an additional variable - only the running variable i.
• greybeard: 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".
• thadeuszlay: @greybeard but I don't know whether it's good practice to mutate the input value.
• morbusg: sorry for nitpicking, but a set – by definition – is a collection of distinct objects.

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

• thadeuszlay: 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]
• Blindman67: @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}
• thadeuszlay: 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: 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.
• Blindman67: @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

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.