• 43.9%

https://leetcode.com/problems/missing-number/#/description

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

Note:

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

https://discuss.leetcode.com/topic/22313/c-solution-using-bit-manipulation

C++ solution using bit manipulation

There are several similar problems in the problem list.

https://discuss.leetcode.com/topic/22305/1-lines-ruby-python-java-c

1+ lines Ruby, Python, Java, C++

Several different solutions, some with O(1) extra space, some with O(n).

Sum of 0..n minus sum of the given numbers is the missing one.

These only use O(1) extra space.

Python

Java

C++

Using long for Java and C++ to prevent overflow (the n*(n+1) overflows ints already for n=46341, and then the /2 causes an actual wrong result).

Xor-ing the given numbers and 0..n.

These use O(n) extra space, but I like them anyway.

Python

Xor-ing with O(1) space

Saw this from ts before. Xoring 0..n results in [n, 1, n+1, 0][n % 4]. You can also spot the pattern by looking at xors of such ranges, and it’s easy to explain as well.

Python

Sum, without formula.

Java and C++:

In Java I believe this is safe, overflow might happen but not cause a wrong result (because another overflow will fix it). In C++ I believe it’s probably safe in the same way, except that that behavior isn’t defined in the standard(s) but is a de-facto standard anyway. In any case, I could just use 64-bit ints again to be safe.

Set/array difference

Don’t know about Ruby’s runtime, might not be linear. Python’s sets are hash sets and the difference is linear time on average. Don’t know about its worst case, and apparently neither does the TimeComplexity page.

Python

https://discuss.leetcode.com/topic/25998/clear-c-solution-that-can-avoid-overflow

Clear C++ solution that can avoid overflow

https://discuss.leetcode.com/topic/22366/simple-c-codes

Simple C++ codes

Using bit XOR operatons, just like the “find missing number (all elements except one occur twice, find the one that occurs once)” one

The reason I didn’t use sum[1..n] - sum(nums) is that calculating sum has potential to cause overflow. XOR bit operation is much safer.

https://discuss.leetcode.com/topic/42439/1-line-python-solution

1 line Python Solution