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

Question

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)\$ and space complexity of \$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;
};

• Peilonrayz: This question is being discussed here: meta.stackexchange.com/q/329996
• KIKO Software: The discussion, mentioned above, was removed because it was deemed off-topic. It's an legal issue, not suited for discussion on Meta (or anywhere?). I made the point that LeetCode's terms say: "You agree not to copy or publish our content.", which makes sense. In general material on the web is copyrighted, unless explicitly stated otherwise. However, one could argue that this is a case of "fair use" because there's only the intent to discuss the problem and not to pirate it.

Answer 1

I don't think there is a better than \$O(n)\$ and \$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 }
 return total;
}

BTW

The extra brackets are not needed when calculate the total

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