Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Problem description

Given an array nums containing n of [0, n], find the number in the range [0, n] that does not appear in the array.

Title link: Missing numbers.

Two, the title requirements

The sample

Input: nums = [9,6,4,2,3,5,7,0,1] output: 8 explanation: n = 9 because there are nine digits, so all the digits are in the range [0,9]. 8 is the missing number because it does not appear in NUMs.Copy the code

inspection

1. Bit operation, xOR problem 2. The recommended time is 10 to 30 minutesCopy the code

Third, problem analysis

In this article, we can find out more about bitwise operation.

Day 45: Bit operation.

Note that the array elements in the question are all different. We need to find the digits in the column 0 to n that are not included in the array. Taking the array as an example, the sorting result is as follows:

0 1 2 3 4 5 6 7 8 9Copy the code

Since it is the topic of bit operation, want to use the relevant knowledge point of operation in place for certain, if this one carries out above two numbers or operation, so same number can be eliminated, and what leave is not the number that is lost?

Symbol: ^

Operation rule: if two bits are opposite, they are 1, and if they are identical, they are 0

Example: 1001 ^ 0111 = 1110

Four, coding implementation

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int i,n=nums.size(),ans=0;// Digital initialization
        for(i=0; i<n; i++)//for loop judgment
        {
            ans=ans^i^nums[i];// Bit by bit xor calculation
        }
        return ans^n;// Output the result}};Copy the code

V. Test results