-5

I'm solving a challenge which has a sequence of integers from 1 to N, and the task is to find the missing integer in the sequence, and the one integer that is duplicated.

The constraints -

You are not allowed to sort the array.

Your solution should not time out for large values of N.

Ideally, your solution should not use extra space except the one provided by the input array (which can be modified).

My current code times out, I'm assuming that's because the complexity for finding the duplicate element might be O(N^2).

For the missing element, my algorithm is -

  1. Create a variable, set it to 1, and loop until condition is true
  2. In loop, check if variable is present in array, if so, increment variable and continue loop
  3. If variable was not found in array, this was the missing element. Break out of loop.

This should run in O(N) time, so this part should be fine.

For the duplicate element, my approach was to check the first index and last index of every element in array. For unique elements, the index values would be the same, but it would be different for the duplicates.

This is where the problem lies, I think.

My code -

function solution(array) {
  var missing = 0,
    duplicate = 0;
  let notFound = true;
  let curr = 1;
  while (notFound) {
    if (array.indexOf(curr) === -1) {
      notFound = false;
      break;
    }
    curr++;
  }
  missing = curr;

  duplicate = array.find((e, i, arr) => arr.indexOf(e) !== arr.lastIndexOf(e));
  return [missing, duplicate];
}

console.log(solution([2, 3, 1, 4, 4, 6]));

I checked some related questions, like this and this, but couldn't get anything out of them.

How do I fix this?

Community
  • 1
  • 1
Manish Giri
  • 3,562
  • 8
  • 45
  • 81
  • a similar question: https://stackoverflow.com/q/44637670/1632887 – seleciii44 Oct 29 '17 at 06:17
  • I'd like to know why my question was downvoted. It's not vague, not opinionated or very broad, not unclear, and not a homework assignment with no research effort. – Manish Giri Oct 29 '17 at 07:33

1 Answers1

1

I think you can hash your input array.
What I mean by that is, suppose your array is [4,1,5,6,3,1]
Here is a simple pseudo-code.
You can get duplicate element like this:

for i:array.length
    array[array[i]] = array[i]*-1 // you found and marked first element of your array
    if(array[i] > 0) //it would be positive if you found and marked an element twice.
        array[array[i]] is the duplicate element

This runs in O(n)

Now to get the missing element, you can traverse the array again

for i:array.length
    if (array[i] > 0 && array[i]!=duplicate element) //there would be two positive numbers, missing number and the duplicate
        i = missing element

This O(n) again, so its O(n) overall. If anything is unclear, you can ask. Sorry about preferring to write a pseudo-code instead of an explanation.

hsnsd
  • 1,728
  • 12
  • 30