268. Missing Number
easyAn array contains n distinct integers from 0 to n with one number missing. Find the missing one in O(n) time and O(1) space using XOR — or a Gaussian-sum subtraction.
By Sam K., Founder, InterviewChamp.AI · Last verified
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.
Constraints
n == nums.length1 <= n <= 10^40 <= nums[i] <= nAll the numbers of nums are unique.
Examples
Example 1
nums = [3,0,1]2Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Example 2
nums = [0,1]2Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
Example 3
nums = [9,6,4,2,3,5,7,0,1]8Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Sum approach: expected = n*(n+1)/2; missing = expected - sum(nums). Watch for integer overflow on large n.
Hint 2
XOR approach: XOR every index 0..n together with every value in nums. Pairs cancel; the missing number survives.
Hint 3
Both are O(n) time and O(1) space — pick whichever you can derive without bugs on the whiteboard.
Solution approach
Reveal approach
XOR approach (overflow-proof). Initialize result = n (since the index range goes 0..n-1 but the value range goes 0..n, we seed with n to cover the boundary). For each index i from 0 to n-1, do result ^= i ^ nums[i]. Every value that appears as both an index and an element cancels out; only the missing value remains. O(n) time, O(1) space. The arithmetic alternative computes expected_sum = n * (n + 1) / 2 then subtracts the actual sum of nums; equally O(n)/O(1) but vulnerable to integer overflow in fixed-width languages on adversarial inputs.
Complexity
- Time
- O(n)
- Space
- O(1)
Related patterns
- bit-manipulation
- xor
- math
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
- Apple
More Bit Manipulation practice problems
- 29. Divide Two Integers
- 78. Subsets
- 89. Gray Code
- 136. Single Number
- 137. Single Number II
- 187. Repeated DNA Sequences
- 190. Reverse Bits
- 191. Number of 1 Bits