~/leetcode75 $
|
Bit Manipulation

13. Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Examples

Example 1

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 so numbers should be in [0,3]. 2 is missing.

Example 2

Input: nums = [0,1]
Output: 2

Example 3

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

Constraints

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique.

Dado un arreglo nums que contiene n numeros distintos en el rango [0, n], devuelve el unico numero del rango que falta en el arreglo.

Ejemplos

Ejemplo 1

Entrada: nums = [3,0,1]
Salida: 2
Explicacion: n = 3 entonces los numeros deben estar en [0,3]. 2 falta.

Ejemplo 2

Entrada: nums = [0,1]
Salida: 2

Ejemplo 3

Entrada: nums = [9,6,4,2,3,5,7,0,1]
Salida: 8

Restricciones

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • Todos los numeros en nums son unicos.
missing_number.py 
from typing import List

# Find the missing number in [0..n] using XOR
nums: List[int] = [9, 6, 4, 2, 3, 5, 7, 0, 1]
ans: int = 0

# XOR all indices from 0 to n
for i in range(len(nums) + 1):
    ans ^= i

# XOR all values in nums; the remaining value is the missing number
for i in nums:
    ans ^= i

print(ans)
Keyboard shortcuts
← h Previous problem
→ l Next problem
Esc Back to index
? Toggle this help