Codility - Perm Missing Elem // C++

문제

 

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

int solution(vector<int> &A);

that, given an array A, returns the value of the missing element.

For example, given array A such that:

A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5

the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..100,000];
• the elements of A are all distinct;
• each element of array A is an integer within the range [1..(N + 1)].

 

1 ~ N(N : 0~100,000) 사이의 정수 중 하나를 제외한 나머지 정수의 값이 하나씩 들어있는 벡터가 있다.

이 때, 벡터 내에 존재 하지 않는 정수를 찾아라.

---

 

풀이

 

bool type의 배열을 선언해서 벡터 전체를 보면서 나왔다면 체크를 해 두고 배열을 다시 탐색해서 나오지 않은 수를 확인했다.

---

 

코드

int solution(vector<int> &A) {
    bool *arr = new bool[A.size() + 2];
    
    for(int i=0;i<A.size()+2;i++)
        arr[i] = false;
        
    for(int i=0;i<A.size();i++)
        arr[A[i]] = true;
        
    for(int i=1;i<A.size()+2;i++)
        if(arr[i] == false)
            return i;
}