# Find missing element in an array of unique elements from 0 to n

Posted on

Problem

The task is taken from LeetCode

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2


Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8


Note:

Your algorithm should run in linear runtime complexity. Could you
implement it using only constant extra space complexity?

My approach is to subtract the sum from 0-n and the sum of the elements in the array. For the sum of the number from 0 to n I use the Gauss forumula: (n * (n + 1)) / 2. For the sum in the array I will have to iterate through the whole array and sum up the elements.

My solution has time complexity of $$O(n)$$

$O\left(n\right)$

$O(n)$ and space complexity of $$O(1)$$

$O\left(1\right)$

$O(1)$.

/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
if (nums.length === 0) return -1;
const sumOfNums = nums.reduce((ac, x) => ac + x);
const sumTillN = (nums.length * (nums.length + 1)) / 2;
return sumTillN - sumOfNums;
};


Solution

I don’t think there is a better than $$O(n)$$

$O\left(n\right)$

$O(n)$ and $$O(1)$$

$O\left(1\right)$

$O(1)$ to this problem.

However you can simplify the code a little (trivial) by subtracting from the expected total.

const findVal = nums => vals.reduce((t, v) => t - v, nums.length * (nums.length + 1) / 2);


Or

function findVal(nums) {
var total = nums.length * (nums.length + 1) / 2;
for (const v of nums) { total -= v }

(x * (x + 1)) / 2 === x * (x + 1) / 2