# Leetcode : 0268. Missing Number (bit)
###### tags:`leetcode`

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <unordered_map>
using std::vector;
using std::unordered_map;
using namespace std;

class BaseVectorPrint {
    public:
        void BasePrint00(vector<int>& num) {
            for (size_t i = 0; i < num.size(); ++i) {
                cout << "[" <<num.at(i) << "]" << "; ";
            }
            cout << endl;
        }

        void BasePrint01(vector<int>& num) {
            for (size_t i = 0; i < num.size(); ++i) {
                cout << num[i] << "; ";
            }
            cout << endl;
        }

        void BasePrint02(vector<int>& num) {
            for (const auto &item : num) {
                cout << item << "; ";
            }
            cout << endl;
        }
        
        void TwoDimensionalPrint(vector<vector<int>> &num){
            for (int i = 0; i < num.size(); i++)
            {
                for (int j = 0; j < num[i].size(); j++)
                {
                    cout << "[" << num[i][j] << "]";
                }
                cout << endl;
            }
        }
};

class Solution00 {
public:
    int missingNumber(vector<int>& nums) {
        int lenth = nums.size();//it get n + 1 
        int total = lenth*(lenth+1)/2; //h * w = total area
        int missing = 0;
        for (int i=0; i<lenth ;i++){
            missing += nums[i]; // miss area
        }
        return (total - missing); //total - miss = lost number
    }
};

class Solution01 {
public:
    int missingNumber(vector<int>& nums) {
        int sum = 0, n = nums.size();
        for (auto &a : nums) {
            sum += a;
        }
        return 0.5 * n * (n + 1) - sum; //total area top*below/2 - sum area = lost number.
    }
};

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int missing = n;
        for (int i = 0 ; i<n ;i++) {
            missing ^= nums[i] ^ i ;
        }
        return missing;
    }
};
//example [0,4,2,1] miss [3] 
//all total n = n+1 [0,1,2,3,4] = 5 is max number 
//step01 set max number 5 
// xor opeator rule
// 1 xor 0 = 1
// 0 xor 1 = 1
// 1 xor 1 = 0
// 0 xor 0 = 0

//5 = 0101
//i = 0  0000 xor 0000
//5 xor 0000 xor 0101 >> 0101
//i = 1 0100 xor 0001 >> 0101
//5 xor 0101 xor 0101 >> 0101
//i = 2 0010 xor 0010 >> 0010
//5 xor 0010 xor 0101 >> 0111 
//i = 3 0111 xor 0011 >> 0100
//ans = 0111 xor 0100 >> 0011

int main(void)
{
    BaseVectorPrint printVector;
    Solution02 runfunc;

    vector<int> test01 = {  9,6,4,2,3,5,7,0,1 };
    vector<int> test02 = {  1,  2,  3,  4 };
    vector<int> test03 = { -1,  1,  0, -3,  3 };
    vector<int> ans ;
    int intans;
    intans = runfunc.missingNumber(test01);
    //printVector.BasePrint00(ans);

    printf("%d\n",intans);
    printf("test\n");
    system("pause");
}

> Tip total area - miss area = missing
> Tip xor sub max number = missing