# L3-PermMissingElem
###### tags: `Codility_lessons`
## Question
https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/
## Key
- 法一) 總和:這題A中的值一定從1開始，所以陣列大小跟最大最小值有關，可以直算出總合，再逐一扣除得到剩下就是消失值，後面有一題是確認permution，起始值就不是1，所以無法從size得到總合

- 法二) 二元搜尋:因為如果某一半的陣列沒有缺失值，代表中位數會等於陣列大小的一半；有缺失值的話，則不等於，再依照大於或小於，往左邊或右邊去尋找
## Reference
## Solution
### Sum Sol.

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    long A_size_plus = A.size()+1;
    long total = (1 + A_size_plus)*A_size_plus / 2;
    
    for(int i = 0; i<A.size(); i++)
    {
        total = total - A[i];
    }
    
    return total;
}

### Binary search Sol.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int l=0,r=nums.size(),mid,ans=nums.size();
        while(l<r)
        {
            mid=l+(r-l)/2;
            if(nums[mid]-mid>0)
            {
                r=mid;
                ans=mid;
            }
            else 
                l=mid+1;
        }
        return ans;
    }
};