Given an array 'nums' with n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
EasyUnlock detailed company stats for this questionUpgrade
Given an array nums that contains n distinct numbers taken from the range [0, n], return the one number in that range that's missing.
Example 1
Input: nums = [3, 0, 1] Output: 2
n is 3, so the range is 0 to 3, and 2 is missing.
Example 2
Input: nums = [0, 1] Output: 2
n is 2, so the range is 0 to 2. The missing number can be n itself.
Constraints
n == nums.length1 <= n <= 10^40 <= nums[i] <= n- All values in
numsare distinct.
Approach
XOR every number from 0 to n together with every value in nums. Each number that's present appears twice and cancels out, so the only value left is the missing one. The indices of nums cover 0 to n - 1, so start with n and fold in each index and value as you go.
Steps
- Set
result = n. - For each index
i, setresult = result ^ i ^ nums[i]. - Return
result.
Complexity
- Time:
O(n). One pass overnums. - Space:
O(1).
Common mistakes
- Starting
resultat0instead ofn. The indices stop atn - 1, so you'd miss the case wherenitself is the answer. - Using the sum formula
n * (n + 1) / 2with fixed-size integers on much larger ranges, where it can overflow. It's fine for these constraints, and the XOR version can't overflow at all.
Related questions
Given arrays A and B, build C with C[i] chosen from A[i] or B[i] so that the smallest missing positive integer of C is as small as possible, and return it.Given an array of n integers and a number k, find the maximum number of elements whose sum is less than k, and return their sum.Given an integer n, return how many integers less than n can be written in base 4 using only the digits 0 and 1.Related courses

Course

Course
Course
