Задача с собеседования в TCS

Дан массив nums, состоящий из различных чисел в диапазоне от 0 до n. Верните единственное число из диапазона, отсутствующее в массиве.

Follow up: можете ли вы реализовать решение с использованием лишь O(1) дополнительной памяти и временной сложностью O(n)?

Пример 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n=3, так как в массиве три числа; таким образом, все числа находятся в диапазоне [0, 3]. Число 2 отсутствует в этом диапазоне, поскольку его нет в массиве nums.

Пример 2:
Input: nums = [0,1]
Output: 2
Explanation: n=2, так как в массиве 2 числа; таким образом, все числа находятся в диапазоне [0, 2]. Число 2 отсутствует в этом диапазоне, поскольку его нет в массиве nums.

Пример 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n=9, так как в массиве 9 чисел; таким образом, все числа находятся в диапазоне [0, 9]. Число 8 отсутствует в этом диапазоне, поскольку его нет в массиве nums.

Ограничения:
n == nums.length
1 <= n <= 10⁴
0 <= nums[i] <= n
Все числа в nums уникальны.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Задача может быть решена арифметическим способом: подсчитываем сумму всех чисел диапазона от 0 до n и вычитаем из неё сумму эл-тов входного массива - разница равняется отсутствующему числу.

Предлагаю разобрать более интересный вариант решения с помощью побитового оператора XOR (исключающего ИЛИ), сравнивающего два бита:
- если биты одинаковые -> 0
- если биты разные -> 1

Применяем XOR для "обнуления" повторяющихся значений из массива nums и полного набора чисел диапазона от 0 до n, используя свойство: a ^ a = 0. Отсутствующее число встретится только один раз и останется в результате по свойству a ^ 0 = a. Предварительная сортировка массива не требуется, так как a ^ b = b ^ a.
- проходим циклом по числам от 0 до n, накапливая XOR в res;
- проходим циклом по массиву nums, также накапливая XOR;
- возвращаем res.

Сложность
O(n) - по времени (проходим двумя циклами по n элементам)
O(1) - по памяти (храним только одну переменную res)

Код
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
res = 0

for i in range(n + 1):
res ^= i

for num in nums:
res ^= num

return res

@algoses