[Codility] Lesson 3 - Time Complexity : PermMissingElem

Lesson 3 - Time Complexity : 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)].

📝 풀이

• N + 1 까지의 숫자들의 포함여부를 저장한다.
• 숫자들의 포함여부를 확인해 포함되지 않는 숫자를 찾아낸다.

💻 구현

static class Solution{

    public int solution(int[] A){
        int answer = 0;
        
        boolean[] contains = new boolean[A.length + 2];
        for(int a : A){
            contains[a] = true;
        }

        for(int i = 1; i < contains.length; i++){
            if(!contains[i]){
                answer = i;
                break;
            }
        }

        return answer;
    }
}