Codility 1. 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)].
Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

💡 풀이

1. 배열을 돌면서 visit 여부 체크만 해주면 쉽게 해결할 수 있는 문제이다.

📝 소스코드

class Solution {
    public int solution(int[] A) {
        boolean[] visit = new boolean[A.length + 2]; // 1 ~ N + 1 visit check
        for(int i = 0; i < A.length; i++) {
            visit[A[i]] = true;
        }

        for(int j = 1; j < visit.length; j++) {
            if(!visit[j]) return j;
        }
        
        return 0;
    }
}