6
\$\begingroup\$

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

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;
}
\$\endgroup\$
  • \$\begingroup\$ 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] \$\endgroup\$ – thadeuszlay Apr 10 at 9:15
  • \$\begingroup\$ @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} \$\endgroup\$ – Blindman67 Apr 10 at 10:41
  • \$\begingroup\$ 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 ); \$\endgroup\$ – thadeuszlay Apr 10 at 15:24
  • \$\begingroup\$ 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. \$\endgroup\$ – thadeuszlay Apr 10 at 15:30
  • \$\begingroup\$ @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 \$\endgroup\$ – Blindman67 Apr 10 at 15:59
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.