Missing Number — LeetCode 268 Python Solution
EasyBit ManipulationArrayHash TableMathBinary SearchSorting
- Problem
- #268
- Pattern
- Bit Manipulation
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Python solution
Python
class Solution:
def missingNumber(self, nums: List[int]) -> int:
return reduce(xor, (i ^ v for i, v in enumerate(nums, 1)))Complexity
| Measure | Complexity |
|---|---|
| Time | O(n), where n is the length of the array |
| Space | O(1) auxiliary |
Pattern: Bit Manipulation
Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 268. Missing Number is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.
The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
On study lists
This problem is on Blind 75 and NeetCode 150.
Frequently asked questions
- How hard is LeetCode 268. Missing Number?
- LeetCode 268. Missing Number is rated Easy on LeetCode.
- What is the time complexity of LeetCode 268. Missing Number?
- The Python solution on this page runs in O(n), where n is the length of the array.
- What is the space complexity of LeetCode 268. Missing Number?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 268. Missing Number cover?
- LeetCode 268. Missing Number is tagged Bit Manipulation, Array, Hash Table, Math, Binary Search and Sorting on LeetCode.