Bit Manipulation XOR tricks
111. Missing Number
You are given an array nums of n different integers, and each of them is between 0 and n, inclusive.
The range from 0 to n holds n + 1 values, but the array holds only n. So exactly one value from the
range is not in the array. Return that value.
The array can be in any order. The value left out can be any value in the range, including 0 and n
itself.
Example 1
Input: nums = [6, 2, 0, 5, 1, 3]
4Explanation: The array has 6 elements, so the range is 0 to 6. The array holds 0, 1, 2, 3, 5 and 6, and the one value it does not hold is 4.
Example 2
Input: nums = [2, 0, 1]
3Explanation: The range is 0 to 3. Every value from 0 to 2 is in the array, so the value left out is n itself, 3.
Example 3
Input: nums = [5, 3, 1, 2, 4]
0Explanation: The range is 0 to 5, and 0 belongs to it. Every value from 1 to 5 is in the array, so the answer is 0.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
n = nums.length1 ≤ n ≤ 1050 ≤ nums[i] ≤ n- All the values in
numsare different.
Clarifying questions
What you would ask an interviewer before writing any code.