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

Задача с собеседования в 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