[Codility] Lesson3. PermMissingElem (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)].

🔮풀이

정말 간단해보였는데 잘 안풀렸던 문제. 

A의 원소값은  1 ~ N+1 이므로 1 ~ N+1개 까지의 sum을 구한뒤 원래 A의 크기만큼인 1 ~ N의 sum을 빼면 구하고자 하는 missing elem 값이 나온다.

sum을 구할때는 값이 크므로 long 타입으로 받아야 한다.

정확하게 문제를 읽어야겠다.

---

🔮코드

 #include <algorithm>

int solution(vector<int> &A) {
    long n = A.size()+1;
    long n_sum = (n * (n+1)) / 2;
    long a_sum = 0;

    for(auto x : A){
        a_sum += x;
    }

    int answer = n_sum - a_sum;
    return answer;
}