Find missing numbers from sequence

Benchmark created on

Preparation HTML

<script>
// Mock data generator
function getRandomNumber() {
  return Math.floor(Math.random() * 100000) + 1;
}

function generateInputs(size = 100) {
  const inputs = [];

  for (let i = 0; i < size; i++) {
    const missingNumbers = new Set();
    while (missingNumbers.size < 2) {
      missingNumbers.add(getRandomNumber());
    }
    const allNumbers = Array.from(
      { length: getRandomNumber() },
      (_, i) => i + 1,
    );
    const inputNumbers = allNumbers.filter((num) => !missingNumbers.has(num));
    inputs.push(inputNumbers);
  }

  return inputs;
}

const generatedInputs = generateInputs(1000);

// -----------------------------------------

// functions

// Binary search
function missingNumbersBinary(nums, numsLength) {
  nums.sort((a, b) => a - b);
  const missing = [];
  let i = 1,
    j = 0;
  while (i <= numsLength && j < nums.length) {
    if (i !== nums[j]) {
      missing.push(i);
      i++;
    } else {
      i++;
      j++;
    }
  }
  while (missing.length < 2) {
    missing.push(i);
    i++;
  }
  return missing;
}

// space complexity O(1)
function missingNumbersSpace(nums, numsLength) {
  let xor = numsLength;
  for (let i = 0; i < numsLength; i++) {
    xor ^= i;
  }
  for (let i = 0; i < nums.length; i++) {
    xor ^= nums[i];
  }
  let set_bit_no = xor & ~(xor - 1);
  let x = 0;
  let y = 0;
  for (let i = 0; i <= numsLength; i++) {
    if ((i & set_bit_no) !== 0) {
      x ^= i;
    } else {
      y ^= i;
    }
  }
  for (let i = 0; i < nums.length; i++) {
    if ((nums[i] & set_bit_no) !== 0) {
      x ^= nums[i];
    } else {
      y ^= nums[i];
    }
  }
  return [x, y];
}
</script>

Test runner

Ready to run.

Testing in
TestOps/sec
With binary search
for (let i = 0; i < generatedInputs.length; i++) {
  const input = generatedInputs[i];
  missingNumbersBinary(input, input.length + 2);
}
ready
Space complexity optimized
for (let i = 0; i < generatedInputs.length; i++) {
  const input = generatedInputs[i];
  missingNumbersSpace(input, input.length + 2);
}
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.