[Lesson 3] PermMissingElem

 

문제

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:
class Solution { public int solution(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)].

 

 

 

풀이

첫번째 시도 score : 80

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // Implement your solution here
    int sum = 0;
    int N = A.size() + 1;
    for(int i= 0; i < A.size(); i++)
    {
        sum += A[i];
    }

    return (N+1)*N/2 - sum;
}

 

 

 

두번째 시도 score : 100

 

정렬(n*log(n))를 이용하여, 오름차순으로 정렬 한 뒤, index와 비교하여 다르다면 리턴해준다.

만약, 범위가 [1~N+1]일 경우 리스트 A의 길이가 N이라면, for문에서 빠진 요소를 찾아내지 못한다.

마지막에 N+1을 리턴해주는 예외처리를 해줘야 한다.

// you can use includes, for example:
#include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    
    sort(A.begin(), A.end());

    for(int i = 0; i < A.size(); i++)
    {
        if(A[i] != i + 1) return i+1;
    }

    return A.size()+1;
}